| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 25 | 13 | 13 | 68.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$을 공백으로 구분하여 출력하라.
가능한 답이 여러 개라면 아무거나 출력해도 된다.
3 1 3 2
3 1 2 3 1 2
$B_{P_A} = (1, \, 3, \,2), \, B_A = (2,\, 3, \,1)$이다. 문제에서 제시한 값은 $(1+2)+(2+1) = 6$이고, 이 값이 최대임을 증명할 수 있다.
4 1 2 3 4
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)$는 아래 조건을 만족한다.
School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 I번