310170: CF1792D. Fixed Prefix Permutations

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Fixed Prefix Permutations

题意翻译

对于一个排列 $p$,定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列,定义排列的运算 $p \cdot q$ 为: - $p \cdot q = r$,$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列,对于每一个 $a_i$,求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少,允许有 $i=j$。 多测,$T \le 10^4$,$\sum n \le 5 \times 10^4$,$m \le 10$

题目描述

You are given $ n $ permutations $ a_1, a_2, \dots, a_n $ , each of length $ m $ . Recall that a permutation of length $ m $ is a sequence of $ m $ distinct integers from $ 1 $ to $ m $ . Let the beauty of a permutation $ p_1, p_2, \dots, p_m $ be the largest $ k $ such that $ p_1 = 1, p_2 = 2, \dots, p_k = k $ . If $ p_1 \neq 1 $ , then the beauty is $ 0 $ . The product of two permutations $ p \cdot q $ is a permutation $ r $ such that $ r_j = q_{p_j} $ . For each $ i $ from $ 1 $ to $ n $ , print the largest beauty of a permutation $ a_i \cdot a_j $ over all $ j $ from $ 1 $ to $ n $ (possibly, $ i = j $ ).

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5 \cdot 10^4 $ ; $ 1 \le m \le 10 $ ) — the number of permutations and the length of each permutation. The $ i $ -th of the next $ n $ lines contains a permutation $ a_i $ — $ m $ distinct integers from $ 1 $ to $ m $ . The sum of $ n $ doesn't exceed $ 5 \cdot 10^4 $ over all testcases.

输出格式


For each testcase, print $ n $ integers. The $ i $ -th value should be equal to the largest beauty of a permutation $ a_i \cdot a_j $ over all $ j $ ( $ 1 \le j \le n $ ).

输入输出样例

输入样例 #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

Input

题意翻译

对于一个排列 $p$,定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列,定义排列的运算 $p \cdot q$ 为: - $p \cdot q = r$,$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列,对于每一个 $a_i$,求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少,允许有 $i=j$。 多测,$T \le 10^4$,$\sum n \le 5 \times 10^4$,$m \le 10$

Output

**固定前缀排列**

**题意翻译**

对于一个排列 $p$,定义其美丽度 $k$ 为
- $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$

若 $p,q$ 均为长度为 $n$ 的排列,定义排列的运算 $p \cdot q$ 为:

- $p \cdot q = r$,$p,q,r$ 均为长度为 $n$ 的排列
- $r_j = q_{p_j}$

现在给出 $n$ 个长度为 $m$ 的排列,对于每一个 $a_i$,求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少,允许有 $i=j$。

多测,$T \le 10^4$,$\sum n \le 5 \times 10^4$,$m \le 10$。

**题目描述**

给定 $ n $ 个长度为 $ m $ 的排列 $ a_1, a_2, \dots, a_n $。回忆一下,长度为 $ 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 $ 的乘积是一个排列 $ r $,使得 $ r_j = q_{p_j} $。

对于每个 $ i $ 从 $ 1 $ 到 $ n $,打印出所有 $ j $ 从 $ 1 $ 到 $ n $(可能 $ i = j $)的排列 $ a_i \cdot a_j $ 的最大美丽值。

**输入输出格式**

**输入格式**

第一行包含一个整数 $ t $($ 1 \le t \le 10^4 $)——测试用例的数量。

每个测试用例的第一行包含两个整数 $ n $ 和 $ m $($ 1 \le n \le 5 \times 10^4 $;$ 1 \le m \le 10 $)——排列的数量和每个排列的长度。

接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。

所有测试用例的 $ n $ 之和不超过 $ 5 \times 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
```**固定前缀排列** **题意翻译** 对于一个排列 $p$,定义其美丽度 $k$ 为 - $p_1=1,p_2=2,\cdots,p_k=k,p_{k+1} \neq k+1$ 若 $p,q$ 均为长度为 $n$ 的排列,定义排列的运算 $p \cdot q$ 为: - $p \cdot q = r$,$p,q,r$ 均为长度为 $n$ 的排列 - $r_j = q_{p_j}$ 现在给出 $n$ 个长度为 $m$ 的排列,对于每一个 $a_i$,求 $a_i \cdot a_j(1 \le j \le n)$ 美丽值最大为多少,允许有 $i=j$。 多测,$T \le 10^4$,$\sum n \le 5 \times 10^4$,$m \le 10$。 **题目描述** 给定 $ n $ 个长度为 $ m $ 的排列 $ a_1, a_2, \dots, a_n $。回忆一下,长度为 $ 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 $ 的乘积是一个排列 $ r $,使得 $ r_j = q_{p_j} $。 对于每个 $ i $ 从 $ 1 $ 到 $ n $,打印出所有 $ j $ 从 $ 1 $ 到 $ n $(可能 $ i = j $)的排列 $ a_i \cdot a_j $ 的最大美丽值。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $($ 1 \le t \le 10^4 $)——测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $($ 1 \le n \le 5 \times 10^4 $;$ 1 \le m \le 10 $)——排列的数量和每个排列的长度。 接下来的 $ n $ 行中的第 $ i $ 行包含一个排列 $ a_i $——$ m $ 个从 $ 1 $ 到 $ m $ 的不同整数。 所有测试用例的 $ n $ 之和不超过 $ 5 \times 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 ```

加入题单

上一题 下一题 算法标签: