心跳排列图 - Problem

注：本题中所有序列下标均从 1 开始。

机器人心脏的跳动，排列成图是什么样的？

你有一个算法竞赛机器人，每分钟心跳 $n$ 次，第 $i$ 次心跳的强度为 $a_i$。这里，$a_1\sim a_n$ 恰为 $1\sim n$ 的一个排列。

设 $A_i$ 为序列 $a$ 删除第 $i$ 个元素后得到的序列，即 $A_i=[a_1,\dots,a_{i-1},a_{i+1},\dots,a_n]$。

对于元素互不相同的序列 $p$，设 $G(p)$ 为一个无向图，有 $|p|$ 个点，编号为 $1\sim |p|$。对于每对正整数 $1\le i\lt j\le |p|$，若 $\forall k\in [i,j]\cap \mathbb{Z}$，都有 $p_k\in [\min(p_i,p_j),\max(p_i,p_j)]$，则 $G(p)$ 中 $i$ 号点和 $j$ 号点有一条边。设 $F(p)$ 为 $G(p)$ 中 $1$ 号点到 $|p|$ 号点的最短路长度，这里一条路径长度定义为其边数。

设 $f(a)=[F(A_1),F(A_2),\dots,F(A_n)]$。

给定长度为 $n$ 的序列 $[b_1,\dots,b_n]$，请你求出任意一个 $1\sim n$ 的排列 $a$，使得 $f(a)=b$。保证有解。

在某些子任务中，算法竞赛机器人小 G 会给你一些“提示”：设 $G_0=G(a)$，设 $path_0$ 为 $G_0$ 中某条 $1$ 到 $n$ 的最短路经过的点构成的集合，设 $path_j$ 为 $G(A_j)$ 中某条起始点到结束点的最短路经过的点构成的集合（注意，为了方便，这里给出的 $path_j$ 中点的编号仍然沿用原图中点的编号，参见样例 2）。则小 G 有可能会额外告诉你所有 $path_j$（包括 $path_0$），也有可能只告诉你 $path_0$，也有可能不给你提示，详见输入格式。

保证给出的提示是正确的，也即一定存在一个满足所有提示的排列。

下发文件中有 checker.cpp，你可以用它来检查自己的输出是否正确。用法是 ./checker input output output，input 和 output 分别为输入文件和你的输出。同时还下发了 testlib.h，请将其和 checker 置于同一目录下来编译 checker。

输入格式

第一行两个正整数，为子任务编号 $S$ 以及数据组数 $T$。

接下来 $T$ 组数据，每组数据格式为：第一行一个正整数 $n$，第二行 $n$ 个正整数 $b_1,\dots,b_n$。

特别地，

若 $S=5$，每组数据还会输入 $n+1$ 行，这 $n+1$ 行里第 $i$ 行是一个长度为 $n$ 的 01 串 $c_i$，$c_{i,j}=[j\in path_{i-1}]$。
若 $S=6$，每组数据还会输入第三行，包含一个长度为 $n$ 的 01 串 $c$，$c_i=[i\in path_0]$。

注意：

即使你的程序不需要用到提示，在 $S=5$ 或 $S=6$ 时你仍然需要读入数组 $c$。
对于一种输入的 $b$，符合条件的 $a$ 可能不唯一，进而 $c$ 可能也不唯一。不要求你的输出符合我们给出的 $c$ 的限制，只要符合 $b$ 的限制即视为正确。

同一行输入的不同变量用一个空格隔开。

输出格式

对于每组数据输出一行 $n$ 个正整数，为你求出的排列 $a$。

样例输入 1

9 11
4
2 2 1 1
4
2 2 2 2
4
2 1 1 2
7
5 5 4 4 4 5 5
7
1 3 2 2 2 2 4
7
3 3 2 4 4 5 3
8
2 2 3 5 3 3 3 4
8
5 4 4 4 4 6 6 5
8
4 4 4 2 4 4 2 3
9
4 7 5 5 5 5 3 4 4
9
3 4 4 4 4 4 4 4 6

样例输出 1

1 2 4 3
2 1 4 3
1 3 2 4
3 1 7 2 6 4 5
3 1 6 4 2 5 7
2 3 1 6 4 7 5
5 6 3 1 7 4 2 8
1 8 2 7 3 5 6 4
6 3 2 7 4 5 1 8
5 8 6 3 7 1 9 2 4
2 9 3 1 8 5 7 6 4

样例 1 解释

考虑样例中的第一组数据。一组解是 $a=[1,2,4,3]$。$A_1,A_2,A_3,A_4$ 分别为 $[2,4,3],[1,4,3],[1,2,3],[1,2,4]$。$G(A_1),G(A_2),G(A_3),G(A_4)$ 四个图中的边分别为：

$G(A_1)$：$(1,2),(2,3)$。因此 $F(A_1)=2$。
$G(A_2)$：$(1,2),(2,3)$。因此 $F(A_2)=2$。
$G(A_3)$：$(1,2),(1,3),(2,3)$。因此 $F(A_3)=1$。
$G(A_4)$：$(1,2),(1,3),(2,3)$。因此 $F(A_4)=1$。

所以 $f(a)=[2,2,1,1]$，符合输入。

符合输入的 $a$ 不唯一，比如 $a=[4,3,1,2]$ 也是正确的。

样例输入 2

样例输出 2

1 2 4 3

样例 2 解释

该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 5 的提示。注意在给出 $path_j$ 时仍然沿用原编号，例如删去 $1$ 后，新的最短路经过的点编号为 $2\to 3\to 4$。

样例输入 3

样例输出 3

1 2 4 3

样例 3 解释

该样例的排列和第一个样例中第一组数据是相同的，但本样例存在子任务 6 的提示。

数据范围

对于所有数据：$1\le T\le 4\times 10^4,4\le n\le 10^5,\sum n\le 5\times 10^5$。

子任务 1（$7$ 分）$T\le 250,n\le 7$。
子任务 2（$5$ 分）$b_i=1$。
子任务 3（$10$ 分）$n\ge 90000$，保证存在一组解满足 $a_1=1,a_n=n$。
子任务 4（$7$ 分）$n\ge 90000$，保证存在一组解满足 $a_2=1,a_{n-1}=n$。
子任务 5（$15$ 分）$n\le 100,\sum n^3\le 3\times 10^6$，存在所有 $path_j$ 的提示。
子任务 6（$15$ 分）$n\le 100,\sum n^3\le 3\times 10^6$，存在 $path_0$ 的提示。
子任务 7（$15$ 分）$n=100,T=3$，共 5 个测试点，输入生成方式是随机一个 $a$ 再求出 $f(a)$ 作为输入。
子任务 8（$25$ 分）$n\le 100,\sum n^3\le 3\times 10^6$。依赖子任务 $1,5,6,7$。
子任务 9（$1$ 分）无特殊限制。依赖子任务 $1\sim 8$。

QOJ.ac

QOJ

2022 集训队互测 Round 5

B. 心跳排列图