시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB25131368.421%

문제

길이 $N$의 순열 $P = (P_1, \, P_2, \, \cdots, \, P_N)$가 주어질 때, 길이 $N$의 적당한 순열 $A = (A_1, \, A_2, \, \cdots, \, A_N)$와 $B = (B_1, \, B_2, \, \cdots, \, B_N)$를 구성하여

$$\displaystyle \large \sum_{k=1}^{N-1} \left( \min \left( B_{P_{A_k}}, B_{P_{A_{k+1}}} \right) + \min \left( B_{A_k}, B_{A_{k+1}} \right) \right)$$

을 최대화하라.

입력

첫 번째 줄에 순열의 길이 $N$이 주어진다. ($2 \leq N \leq 200 \, 000$)

두 번째 줄에 순열 $P$의 원소 $P_1, \, P_2, \, \cdots, \, P_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주어진 식을 최대화하는 순열 $A$의 원소 $A_1, \, A_2,\, \cdots, \, A_N$을 공백으로 구분하여 출력하라.

두 번째 줄에 주어진 식을 최대화하는 순열 $B$의 원소 $B_1, \, B_2,\, \cdots, \, B_N$을 공백으로 구분하여 출력하라.

가능한 답이 여러 개라면 아무거나 출력해도 된다.

예제 입력 1

3
1 3 2

예제 출력 1

3 1 2
3 1 2

$B_{P_A} = (1, \, 3, \,2), \, B_A = (2,\, 3, \,1)$이다. 문제에서 제시한 값은 $(1+2)+(2+1) = 6$이고, 이 값이 최대임을 증명할 수 있다.

예제 입력 2

4
1 2 3 4

예제 출력 2

1 2 3 4
1 2 3 4

$B_{P_A} = (1,\, 2, \,3,\,4), \, B_A = (1, \,2,\, 3,\, 4)$이다. 문제에서 제시한 값은 $(1+2+3)+(1+2+3) = 12$이고, 이 값이 최대임을 증명할 수 있다.

노트

길이가 $N$인 순열이란 순열의 원소로 $1$부터 $N$까지의 정수가 모두 빠짐없이 단 한 번씩 나오는 수열을 의미한다. 즉, 순열 $A = \left(A_1, \, A_2 , \, \cdots, \, A_N\right)$는 아래 조건을 만족한다.

  •  $A_i$는 $1$ 이상 $N$ 이하의 정수
  •  $i \neq j$이면 $A_i \neq A_j$ 

출처

School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 I번