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

\\n

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

\\n

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

\\n

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

\\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|$ 号点的最短路长度，这里一条路径长度定义为其边数。

\\n

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

\\n

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

\\n

在某些子任务中，算法竞赛机器人小 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$，也有可能不给你提示，详见输入格式。

\\n

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

\\n

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

\\n

输入格式

\\n

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

\\n

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

\\n

特别地，

\\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]$。

注意：

\\n

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

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

\\n

输出格式

\\n

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

\\n

样例输入 1

\\n

统计

递交统计

[集训队互测 2023day5]心跳排列图

信息

状态

开发

支持

登录