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

Problem Description

Just A Grid City (JAG City) has NN horizontal roads and NN vertical roads. These roads form a square grid. The distance between any two neighboring parallel roads is 11. The horizontal roads are numbered from 11 to NN from top to bottom, and the vertical roads are numbered from 11 to NN from left to right. We call the intersection of horizontal road ii and vertical road jj (i,j)(i,j).

A marathon will be held on the roads of JAG City. To make the runners visit many parts of the city, the organizers have placed NN checkpoints. You are given a permutation P=(P1,P2,…,PN)P=(P_1,P_2,\ldots,P_N) of (1,2,…,N)(1,2,\ldots,N). The checkpoints are placed at (i,Pi)(i,P_i) (i=1,2,…,Ni=1,2,\ldots,N).

The organizers want the course to be easy to follow. Therefore, the marathon course must satisfy all of the following conditions:

  • The course is a closed route that uses only the roads.
  • The course uses all NN horizontal roads and all NN vertical roads, traveling a distance of at least 11 along every road.
  • The course passes through every checkpoint and turns at every checkpoint.
  • The course has exactly 2N2N turns.

The course may cross itself, even at intersections where it does not turn. At each turn, the course switches from a horizontal road to a vertical road or vice versa.

A route is valid if it satisfies all the conditions above. It is guaranteed that at least one valid route exists. Among all valid routes, output one with the maximum possible length.

Four marathon courses: valid but not optimal, optimal, invalid, and invalid. Circles mark checkpoints.

Figure E-1: Examples of valid and invalid marathon courses

Figure E-1 shows four routes for the sample input. The leftmost route is valid but not optimal; its length is 1212. The second route is optimal, with length 1414. Although it crosses itself at two intersections where it does not turn, such crossings are allowed. The third route is invalid because it passes through a checkpoint without turning there. The rightmost route is invalid because it has more than 2N2N turns.

Input Format

The input consists of a single test case of the following format.

N
P_1 P_2 ... P_N

The first line contains an integer NN (2≤N≤2×1052\le N\le 2\times 10^5), representing the number of roads in each direction.

The second line contains NN distinct integers P1,P2,…,PNP_1,P_2,\ldots,P_N (1≤Pi≤N1\le P_i\le N), which form the permutation PP.

Output Format

Let LL be the maximum possible length of a valid route.

Output LL and the 2N2N intersections at which a valid route of length LL turns, in the order in which they are visited along the course, in the following format:

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

For each ii (1≤i≤2N1\le i\le 2N), the pair (Xi,Yi)(X_i,Y_i) represents the intersection of horizontal road XiX_i and vertical road YiY_i, where 1≤Xi,Yi≤N1\le X_i,Y_i\le N.

If there are multiple valid routes of length LL, you may output any of them.

You may choose any turning intersection as (X1,Y1)(X_1,Y_1) and output the intersections in either direction along the course.

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