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

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, visits its starting point only at the start and at the end, and does not visit any other point more than once.
  • 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.

In particular, the course must not 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.

Figure I-1

Figure I-1: Examples of valid and invalid marathon courses.

Figure I-1 shows examples of valid and invalid routes for the sample input. The leftmost route is valid because it satisfies all the conditions. The second route is invalid because it crosses itself. The third route is invalid because it has more than 2N2N turns. The rightmost route is invalid because it does not turn at every checkpoint.

Output one marathon course that satisfies all the conditions. It is guaranteed that such a course exists under the given constraints.

Note that you do not need to maximize or minimize the total length of the course.

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\le2\times10^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 a permutation PP.

Output Format

Output the 2N2N intersections at which the course turns, in the order in which they are visited along the course, in the following format:

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

For each ii (1≤i≤2N1\le i\le2N), 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, 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
2 4
1 4
1 2
3 2
3 1
4 1
4 3
2 3