33OJ
登录 注册

#P17530. [JAG 2026 Summer Camp #1] JAG City Marathon I

    ID: 20260 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>贪心Special Judge构造ICPC2026

[JAG 2026 Summer Camp #1] JAG City Marathon I

题目描述

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

JAG 城市的道路上即将举行一场马拉松。为了让跑者经过城市中的更多地方,组织者设置了 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 次。

路线允许自交,即使交叉发生在路线不转弯的交点处也可以。每次转弯时,路线从水平道路转入竖直道路,或从竖直道路转入水平道路。

若一条路线满足上述所有条件,则称其为合法路线。保证至少存在一条合法路线。在所有合法路线中,输出一条长度最大的路线。

四条马拉松路线,从左到右依次为合法但非最优、最优、不合法、不合法;圆圈表示检查点。

图 E-1:合法与不合法的马拉松路线示例。图中从左到右的标签分别表示“合法但非最优”“最优”“不合法”“不合法”;Checkpoint 表示检查点。

图 E-1 展示了样例输入对应的四条路线。最左边的路线合法但非最优,长度为 1212。第二条路线最优,长度为 1414。虽然它在两个不转弯的交点处自交,但这样的交叉是允许的。第三条路线不合法,因为它经过了一个检查点,却没有在那里转弯。最右边的路线不合法,因为它的转弯次数超过了 2N2N。

输入格式

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

N
P_1 P_2 ... P_N

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

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

输出格式

设 LL 为合法路线的最大可能长度。

输出 LL,以及一条长度为 LL 的合法路线的 2N2N 个转弯交点。交点按照沿路线经过的顺序输出,格式如下:

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

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

若有多条长度为 LL 的合法路线,可以输出其中任意一条。

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

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