310005: CF1770H. Koxia, Mahiru and Winter Festival
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Koxia, Mahiru and Winter Festival
题目描述
Wow, what a big face! Kagura Mahiru Koxia and Mahiru are enjoying the Winter Festival. The streets of the Winter Festival can be represented as a $ n \times n $ undirected grid graph. Formally, the set of vertices is $ \{(i,j) \; | \; 1 \leq i,j\leq n \} $ and two vertices $ (i_1,j_1) $ and $ (i_2,j_2) $ are connected by an edge if and only if $ |i_1-i_2|+|j_1-j_2|=1 $ .  A network with size $ n = 3 $ .Koxia and Mahiru are planning to visit The Winter Festival by traversing $ 2n $ routes. Although routes are not planned yet, the endpoints of the routes are already planned as follows: - In the $ i $ -th route, they want to start from vertex $ (1, i) $ and end at vertex $ (n, p_i) $ , where $ p $ is a permutation of length $ n $ . - In the $ (i+n) $ -th route, they want to start from vertex $ (i, 1) $ and end at vertex $ (q_i, n) $ , where $ q $ is a permutation of length $ n $ .  A network with size $ n = 3 $ , points to be connected are shown in the same color for $ p = [3, 2, 1] $ and $ q = [3, 1, 2] $ .Your task is to find a routing scheme — $ 2n $ paths where each path connects the specified endpoints. Let's define the congestion of an edge as the number of times it is used (both directions combined) in the routing scheme. In order to ensure that Koxia and Mahiru won't get too bored because of traversing repeated edges, please find a routing scheme that minimizes the maximum congestion among all edges.  An example solution — the maximum congestion is $ 2 $ , which is optimal in this case.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 2 \leq n \leq 200 $ ) — the size of the network. The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \leq p_i \leq n $ ). The third line contains $ n $ integers $ q_1, q_2, \dots, q_n $ ( $ 1 \leq q_i \leq n $ ). It is guaranteed that both $ p $ and $ q $ are permutations of length $ n $ .
输出格式
Output $ 2n $ lines, each line describing a route. The first $ n $ lines should describe the connections from top to bottom. The $ i $ -th line should describe the route starting at vertex $ (1, i) $ and ending at vertex $ (n, p_i) $ . The next $ n $ lines should describe the connections from left to right. The $ (i+n) $ -th line should describe the route starting at vertex $ (i, 1) $ and ending at vertex $ (q_i, n) $ . Each line describing a route should start with an integer $ k $ ( $ 2 \le k \le 10^5 $ ) — the number of vertices the route passes, including the starting and ending vertices. Then output all the vertices on the route in order. In other words, if the route is $ (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k) $ , then output $ k~x_1~y_1~x_2~y_2 \ldots x_k~y_k $ . Note that $ |x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 $ should holds for $ 1 \le i < k $ . If there are multiple solutions that minimize the maximum congestion, you may output any.
输入输出样例
输入样例 #1
3
3 2 1
3 1 2输出样例 #1
5 1 1 2 1 2 2 3 2 3 3
3 1 2 2 2 3 2
5 1 3 1 2 1 1 2 1 3 1
5 1 1 1 2 1 3 2 3 3 3
4 2 1 2 2 2 3 1 3
4 3 1 3 2 3 3 2 3输入样例 #2
4
3 4 2 1
2 4 1 3输出样例 #2
6 1 1 1 2 2 2 2 3 3 3 4 3
6 1 2 1 3 2 3 2 4 3 4 4 4
5 1 3 2 3 2 2 3 2 4 2
7 1 4 1 3 1 2 2 2 2 1 3 1 4 1
7 1 1 2 1 3 1 3 2 3 3 2 3 2 4
6 2 1 2 2 3 2 4 2 4 3 4 4
6 3 1 3 2 3 3 3 4 2 4 1 4
5 4 1 4 2 4 3 3 3 3 4输入样例 #3
3
1 2 3
1 2 3输出样例 #3
3 1 1 2 1 3 1
3 1 2 2 2 3 2
3 1 3 2 3 3 3
3 1 1 1 2 1 3
3 2 1 2 2 2 3
3 3 1 3 2 3 3说明
The first example corresponds to the figures in the problem statement. The output for examples $ 2 $ and $ 3 $ respectively are visualized below:  Sample output for examples $ 2 $ and $ 3 $ . Maximum congestions are $ 2 $ and $ 1 $ respectively.Input
暂时还没有翻译
Output
**题目描述**
Koxia和Mahiru正在享受冬季节日。冬季节日的街道可以表示为一个$ n \times n $的无向网格图。形式上，顶点集合是$ \{(i,j) \; | \; 1 \leq i,j\leq n \} $，如果满足$ |i_1-i_2|+|j_1-j_2|=1 $，则两个顶点$ (i_1,j_1) $和$ (i_2,j_2) $之间通过一条边连接。
Koxia和Mahiru计划通过遍历$ 2n $条路线来参观冬季节日。尽管路线尚未规划，但路线的端点已经规划如下：
- 在第$ i $条路线上，他们想从顶点$ (1, i) $开始，结束于顶点$ (n, p_i) $，其中$ p $是一个长度为$ n $的排列。
- 在第$ (i+n) $条路线上，他们想从顶点$ (i, 1) $开始，结束于顶点$ (q_i, n) $，其中$ q $是一个长度为$ n $的排列。
任务是找到一个路由方案——$ 2n $条路径，每条路径连接指定的端点。定义边的拥塞为在路由方案中使用的次数（双向合计）。为了确保Koxia和Mahiru不会因为重复经过边缘而感到无聊，请找到一个路由方案，使所有边中的最大拥塞最小化。
**输入输出格式**
**输入格式**
第一行包含一个整数$ n $（$ 2 \leq n \leq 200 $）——网络的大小。
第二行包含$ n $个整数$ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。
第三行包含$ n $个整数$ q_1, q_2, \dots, q_n $（$ 1 \leq q_i \leq n $）。
保证$ p $和$ q $都是长度为$ n $的排列。
**输出格式**
输出$ 2n $行，每行描述一条路线。
前$ n $行应描述从上到下的连接。第$ i $行应描述从顶点$ (1, i) $开始，到顶点$ (n, p_i) $结束的路线。
接下来的$ n $行应描述从左到右的连接。第$ (i+n) $行应描述从顶点$ (i, 1) $开始，到顶点$ (q_i, n) $结束的路线。
描述路线的每一行应以一个整数$ k $开始（$ 2 \le k \le 10^5 $）——路线经过的顶点数，包括起始和结束顶点。然后按顺序输出路线上的所有顶点。换句话说，如果路线是$ (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k) $，则输出$ k~x_1~y_1~x_2~y_2 \ldots x_k~y_k $。注意，对于$ 1 \le i < k $，应满足$ |x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 $。
如果有多个解可以最小化最大拥塞，则可以输出任意一个。**题目描述** Koxia和Mahiru正在享受冬季节日。冬季节日的街道可以表示为一个$ n \times n $的无向网格图。形式上，顶点集合是$ \{(i,j) \; | \; 1 \leq i,j\leq n \} $，如果满足$ |i_1-i_2|+|j_1-j_2|=1 $，则两个顶点$ (i_1,j_1) $和$ (i_2,j_2) $之间通过一条边连接。 Koxia和Mahiru计划通过遍历$ 2n $条路线来参观冬季节日。尽管路线尚未规划，但路线的端点已经规划如下： - 在第$ i $条路线上，他们想从顶点$ (1, i) $开始，结束于顶点$ (n, p_i) $，其中$ p $是一个长度为$ n $的排列。 - 在第$ (i+n) $条路线上，他们想从顶点$ (i, 1) $开始，结束于顶点$ (q_i, n) $，其中$ q $是一个长度为$ n $的排列。 任务是找到一个路由方案——$ 2n $条路径，每条路径连接指定的端点。定义边的拥塞为在路由方案中使用的次数（双向合计）。为了确保Koxia和Mahiru不会因为重复经过边缘而感到无聊，请找到一个路由方案，使所有边中的最大拥塞最小化。 **输入输出格式** **输入格式** 第一行包含一个整数$ n $（$ 2 \leq n \leq 200 $）——网络的大小。 第二行包含$ n $个整数$ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。 第三行包含$ n $个整数$ q_1, q_2, \dots, q_n $（$ 1 \leq q_i \leq n $）。 保证$ p $和$ q $都是长度为$ n $的排列。 **输出格式** 输出$ 2n $行，每行描述一条路线。 前$ n $行应描述从上到下的连接。第$ i $行应描述从顶点$ (1, i) $开始，到顶点$ (n, p_i) $结束的路线。 接下来的$ n $行应描述从左到右的连接。第$ (i+n) $行应描述从顶点$ (i, 1) $开始，到顶点$ (q_i, n) $结束的路线。 描述路线的每一行应以一个整数$ k $开始（$ 2 \le k \le 10^5 $）——路线经过的顶点数，包括起始和结束顶点。然后按顺序输出路线上的所有顶点。换句话说，如果路线是$ (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k) $，则输出$ k~x_1~y_1~x_2~y_2 \ldots x_k~y_k $。注意，对于$ 1 \le i < k $，应满足$ |x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 $。 如果有多个解可以最小化最大拥塞，则可以输出任意一个。
Koxia和Mahiru正在享受冬季节日。冬季节日的街道可以表示为一个$ n \times n $的无向网格图。形式上，顶点集合是$ \{(i,j) \; | \; 1 \leq i,j\leq n \} $，如果满足$ |i_1-i_2|+|j_1-j_2|=1 $，则两个顶点$ (i_1,j_1) $和$ (i_2,j_2) $之间通过一条边连接。
Koxia和Mahiru计划通过遍历$ 2n $条路线来参观冬季节日。尽管路线尚未规划，但路线的端点已经规划如下：
- 在第$ i $条路线上，他们想从顶点$ (1, i) $开始，结束于顶点$ (n, p_i) $，其中$ p $是一个长度为$ n $的排列。
- 在第$ (i+n) $条路线上，他们想从顶点$ (i, 1) $开始，结束于顶点$ (q_i, n) $，其中$ q $是一个长度为$ n $的排列。
任务是找到一个路由方案——$ 2n $条路径，每条路径连接指定的端点。定义边的拥塞为在路由方案中使用的次数（双向合计）。为了确保Koxia和Mahiru不会因为重复经过边缘而感到无聊，请找到一个路由方案，使所有边中的最大拥塞最小化。
**输入输出格式**
**输入格式**
第一行包含一个整数$ n $（$ 2 \leq n \leq 200 $）——网络的大小。
第二行包含$ n $个整数$ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。
第三行包含$ n $个整数$ q_1, q_2, \dots, q_n $（$ 1 \leq q_i \leq n $）。
保证$ p $和$ q $都是长度为$ n $的排列。
**输出格式**
输出$ 2n $行，每行描述一条路线。
前$ n $行应描述从上到下的连接。第$ i $行应描述从顶点$ (1, i) $开始，到顶点$ (n, p_i) $结束的路线。
接下来的$ n $行应描述从左到右的连接。第$ (i+n) $行应描述从顶点$ (i, 1) $开始，到顶点$ (q_i, n) $结束的路线。
描述路线的每一行应以一个整数$ k $开始（$ 2 \le k \le 10^5 $）——路线经过的顶点数，包括起始和结束顶点。然后按顺序输出路线上的所有顶点。换句话说，如果路线是$ (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k) $，则输出$ k~x_1~y_1~x_2~y_2 \ldots x_k~y_k $。注意，对于$ 1 \le i < k $，应满足$ |x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 $。
如果有多个解可以最小化最大拥塞，则可以输出任意一个。**题目描述** Koxia和Mahiru正在享受冬季节日。冬季节日的街道可以表示为一个$ n \times n $的无向网格图。形式上，顶点集合是$ \{(i,j) \; | \; 1 \leq i,j\leq n \} $，如果满足$ |i_1-i_2|+|j_1-j_2|=1 $，则两个顶点$ (i_1,j_1) $和$ (i_2,j_2) $之间通过一条边连接。 Koxia和Mahiru计划通过遍历$ 2n $条路线来参观冬季节日。尽管路线尚未规划，但路线的端点已经规划如下： - 在第$ i $条路线上，他们想从顶点$ (1, i) $开始，结束于顶点$ (n, p_i) $，其中$ p $是一个长度为$ n $的排列。 - 在第$ (i+n) $条路线上，他们想从顶点$ (i, 1) $开始，结束于顶点$ (q_i, n) $，其中$ q $是一个长度为$ n $的排列。 任务是找到一个路由方案——$ 2n $条路径，每条路径连接指定的端点。定义边的拥塞为在路由方案中使用的次数（双向合计）。为了确保Koxia和Mahiru不会因为重复经过边缘而感到无聊，请找到一个路由方案，使所有边中的最大拥塞最小化。 **输入输出格式** **输入格式** 第一行包含一个整数$ n $（$ 2 \leq n \leq 200 $）——网络的大小。 第二行包含$ n $个整数$ p_1, p_2, \dots, p_n $（$ 1 \leq p_i \leq n $）。 第三行包含$ n $个整数$ q_1, q_2, \dots, q_n $（$ 1 \leq q_i \leq n $）。 保证$ p $和$ q $都是长度为$ n $的排列。 **输出格式** 输出$ 2n $行，每行描述一条路线。 前$ n $行应描述从上到下的连接。第$ i $行应描述从顶点$ (1, i) $开始，到顶点$ (n, p_i) $结束的路线。 接下来的$ n $行应描述从左到右的连接。第$ (i+n) $行应描述从顶点$ (i, 1) $开始，到顶点$ (q_i, n) $结束的路线。 描述路线的每一行应以一个整数$ k $开始（$ 2 \le k \le 10^5 $）——路线经过的顶点数，包括起始和结束顶点。然后按顺序输出路线上的所有顶点。换句话说，如果路线是$ (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k) $，则输出$ k~x_1~y_1~x_2~y_2 \ldots x_k~y_k $。注意，对于$ 1 \le i < k $，应满足$ |x_i-x_{i+1}|+|y_i-y_{i+1}| = 1 $。 如果有多个解可以最小化最大拥塞，则可以输出任意一个。