A15698 | $Fixed Prefix Permutations$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定 $n$ 个排列 $a_1, a_2, \dots, a_n$，每个排列长度为 $m$。回忆一下，长度为 $m$ 的排列是 $1$ 到 $m$ 的 $m$ 个互不相同的整数的序列。 一个排列 $p_1, p_2, \dots, p_m$ 的美丽值定义为最大的 $k$，使得 $p_1 = 1, p_2 = 2, \dots, p_k = k$。如果 $p_1 \neq 1$，则美丽值为 $0$。 两个排列 $p$ 和 $q$ 的乘积 $p \cdot q$ 是一个排列 $r$，其中 $r_j = q_{p_j}$。 对于每个 $i$ 从 $1$ 到 $n$，请输出排列 $a_i \cdot a_j$ 在所有 $j$ 从 $1$ 到 $n$（可能 $i = j$）中美丽值的最大值。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5 \cdot 10^4$；$1 \le m \le 10$），分别表示排列的数量和每个排列的长度。 接下来的 $n$ 行，每行包含一个排列 $a_i$，即 $m$ 个互不相同的整数，范围从 $1$ 到 $m$。 所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^4$。

输出格式

对于每个测试用例，输出 $n$ 个整数。第 $i$ 个数表示对于所有 $j$（$1 \le j \le n$），排列 $a_i \cdot a_j$ 的最大美丽值。

输入输出样例

输入 #1

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

输出 #1

1 4 4 
2 2 
10 8 1 6 8 10 1 7

C++ 编辑器

输入

输出

A15698 | Fixed Prefix Permutations

题目描述

输入格式

输出格式

输入输出样例

A15698 | $Fixed Prefix Permutations$