33OJ
登录 注册

#P17580. [JAG 2026 Summer Camp #3] JAG City Marathon II

    ID: 20288 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>Special Judge构造ICPC2026

[JAG 2026 Summer Camp #3] JAG City Marathon II

题目描述

Just A Grid City(简称 JAG City)有 NN 条水平道路和 NN 条竖直道路。这些道路构成一个正方形网格。任意两条相邻的平行道路之间的距离为 11。水平道路从上到下编号为 11 到 NN,竖直道路从左到右编号为 11 到 NN。我们将第 ii 条水平道路与第 jj 条竖直道路的交点称为 (i,j)(i,j)。

JAG City 将在这些道路上举办一场马拉松。为了让跑者经过城市中的许多地方,组织者设置了 NN 个检查点。给定 (1,2,…,N)(1,2,\ldots,N) 的一个排列 P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N),检查点位于 (i,Pi)(i,P_i)(i=1,2,…,Ni=1,2,\ldots,N)。

组织者希望赛道易于遵循。因此,马拉松赛道必须满足以下全部条件:

  • 赛道是一条只沿道路行进的闭合路线。仅在出发和结束时经过起点,其他任意点均不能经过超过一次。
  • 赛道使用全部 NN 条水平道路和全部 NN 条竖直道路,且沿每条道路行进的距离至少为 11。
  • 赛道经过每个检查点,且在每个检查点都转弯。
  • 赛道恰好转弯 2N2N 次。

特别地,赛道不能自交,即使是在不转弯的道路交点处也不行。每次转弯时,赛道都会从水平道路转入竖直道路,或从竖直道路转入水平道路。

满足上述全部条件的路线称为合法路线。

图 I-1

图 I-1:合法与不合法的马拉松赛道示例。图中 Checkpoint 表示检查点,Valid 表示合法,Invalid 表示不合法。

图 I-1 展示了样例输入对应的合法与不合法路线。最左侧的路线满足全部条件,因此合法。第二条路线发生自交,因此不合法。第三条路线的转弯次数超过 2N2N,因此不合法。最右侧的路线没有在每个检查点都转弯,因此不合法。

请输出一条满足全部条件的马拉松赛道。保证在给定约束下存在这样的赛道。

注意,你不需要最大化或最小化赛道的总长度。

输入格式

输入包含一组测试数据,格式如下。

N
P_1 P_2 ... P_N

第一行包含一个整数 NN(2≤N≤2×1052\le N\le2\times10^5),表示每个方向上的道路数量。

第二行包含 NN 个互不相同的整数 P1,P2,…,PNP_1,P_2,\ldots,P_N(1≤Pi≤N1\le P_i\le N),它们组成排列 PP。

输出格式

按照沿赛道经过的顺序,输出赛道转弯的 2N2N 个道路交点,格式如下:

X_1 Y_1
X_2 Y_2
...
X_{2N} Y_{2N}

对于每个 ii(1≤i≤2N1\le i\le2N),(Xi,Yi)(X_i,Y_i) 表示第 XiX_i 条水平道路与第 YiY_i 条竖直道路的交点,其中 1≤Xi,Yi≤N1\le X_i,Y_i\le N。

如果存在多条合法路线,输出任意一条即可。

你可以选择任意一个转弯交点作为 (X1,Y1)(X_1,Y_1),并沿赛道的任意一个方向输出这些交点。

4
2 4 1 3
2 4
1 4
1 2
3 2
3 1
4 1
4 3
2 3