| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 32 | 19 | 16 | 69.565% |
신촌역 지하에서는 한별이가 비밀리에 괴수를 위한 꽃밭을 만들고 있었다. 이제 앞으로 $N$개의 구역만 더 채우면 꽃밭을 완성할 수 있다!
$N$개의 구역은 좌우로 일렬로 나열되어 있으며, 왼쪽부터 순서대로 $1$번부터 $N$번까지 번호가 매겨져 있다. 한별이는 이 구역들에 $1$번부터 $N$번까지 번호가 매겨진 서로 다른 $N$종류의 씨앗을 구역마다 한 종류씩 심었다. 그중 $i$번 씨앗은 $i$장의 꽃잎이 달린 꽃을 피운다.
한별이는 구역을 둘러볼 때 구역마다 새로움을 느낄 수 있었으면 좋겠다고 생각했다. 이를 위해 한별이는 꽃이 모두 피었을 때 $1$번 구역부터 $N$번 구역까지 순서대로 둘러보면, 매 구역에서 이전까지 본 모든 꽃보다 꽃잎의 수가 적거나, 이전까지 본 모든 꽃보다 꽃잎의 수가 많도록 씨앗을 심었다.
한별이는 $N$번 구역까지 이동하며 씨앗을 심은 뒤 꽃을 자라나게 하기 위해 괴수를 자신이 있는 곳으로 불렀다. 괴수는 성대의 구조를 바꿔 $1$번부터 $N$번까지 번호가 매겨진 $N$가지의 음색으로 노래할 수 있는데, 그중 $i$번 음색은 $i$번 씨앗이 즉시 자라나 꽃을 피우도록 만든다. $i$번 씨앗이 아닌 다른 씨앗은 자라나지 않으며, 괴수가 있는 구역 바깥의 씨앗들 역시 자라나지 않는다.
괴수가 어떤 구역에서 인접한 다른 구역으로 이동하는 데 $1$초가 걸리며, 성대의 구조를 바꾸는 데에는 음색 번호의 차이만큼 시간이 걸린다. 예를 들어 $2$번 음색을 내는 성대에서 $5$번 음색을 내는 성대로 구조를 바꾸려면 $\vert 2-5 \vert = 3$초의 시간이 필요하다. 노래를 부르고 꽃이 피어나는 시간은 무시할 수 있을 정도로 짧다. 성대의 구조를 바꾸면서 동시에 다른 구역으로 이동할 수는 없다.
괴수는 현재 $N$번 구역에 있다. 한별이와 괴수는 $15$분 뒤에 열리는 SUAPC에 참여하기 위해 $15$분 안에 모든 꽃을 피우기로 결심했다. $1 \le i \le N$인 모든 $i$에 대해, 괴수가 현재 $i$번 음색으로 노래할 수 있을 때 $15$분 안에 모든 구역의 꽃을 피우는 방법을 찾아라. 모든 꽃을 피우는 데 걸리는 시간을 최소화할 필요는 없음에 유의하라.
첫 번째 줄에 구역의 수 $N$이 주어진다. ($2 \le N \le 240$)
두 번째 줄에 각 구역에 심긴 씨앗의 번호를 나타내는 $N$개의 서로 다른 정수 $A_1 , A_2, \dots , A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le N$)
괴수가 처음으로 낼 수 있는 음색 별로 두 줄씩, 총 $2N$개의 줄을 출력해야 한다. 그중 $2i-1$, $2i$번째 줄은 괴수가 처음에 $i$번 음색을 낼 수 있는 상황에 대한 답이다.
$2i-1$번째 줄에는 모든 꽃을 피우기 위해 필요한 행동 수 $k$를 출력한다. 이 값은 $1\,000$ 이하의 양의 정수여야 한다.
$2i$번째 줄에는 괴수가 한 행동을 나타내는 $k$개의 정수들을 행동 순서대로 공백으로 구분해 출력한다.
-1을 출력한다.0을 출력한다.출력한 행동을 모두 수행했을 때 모든 구역의 꽃이 피어나야 하며, 걸리는 시간의 총합은 $15$분 = $900$초 이하여야 한다. 괴수가 꽃밭의 범위를 벗어나 이동하는 경우 오답으로 처리된다.
만약 조건을 만족하면서 모든 구역에 꽃을 피울 수 없는 경우, 대신 $2i-1$, $2i$번째 줄에 각각 -1을 출력한다.
4 2 3 1 4
7 4 -1 1 -1 3 -1 2 19 1 2 3 4 -1 1 2 3 4 -1 1 2 3 4 -1 1 2 3 4 9 -1 -1 -1 2 0 0 1 0 4 6 -1 1 -1 3 -1 2
처음에 $1$번 음색을 낼 수 있는 경우, 예제의 방법으로 $12$초만에 모든 구역에 꽃을 피울 수 있다.
처음에 $2$번 음색을 낼 수 있는 경우 예제의 방법은 다음과 같다.
해당 방법대로면 $23$초 째에 모든 구역에 꽃이 피지만, 출력한 행동이 모두 끝나는 데에는 $25$초가 필요하므로 채점기는 $25$초가 소요된 것으로 판정한다.
처음에 $3$번 음색을 낼 수 있는 경우, 예제의 방법으로 $11$초만에 모든 구역에 꽃을 피울 수 있다.
처음에 $4$번 음색을 낼 수 있는 경우, $4$번 구역에 즉시 꽃이 핀다. 따라서 처음에 $1$번 음색을 낼 수 있는 경우의 답에서 처음에 $4$번 음색을 내도록 성대 구조를 바꾸지 않고 나머지 행동을 순서대로 시행해 $9$초만에 모든 구역에 꽃을 피울 수 있다.