시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 (추가 시간 없음) | 1024 MB | 286 | 86 | 59 | 32.418% |
위에서부터 1, 2, ..., N이 적혀 있는 카드 한 벌이 있다. 이 때, 1 ≤ x ≤ y ≤ N인 두 정수 x, y에 대해 다음 쿼리를 수행한다.
리플 셔플은 N장의 카드가 있을 때 카드를 위에서부터 ⌊(N + 1) / 2⌋장의 카드 덩어리와 나머지 덩어리로 나눈 후 교대로 카드를 두는 방식으로 카드를 섞는 것이다. 섞기 전에 제일 위에 있었던 카드가 섞은 후에도 제일 위로 오도록 한다.
첫 줄에 카드 수 N(1 ≤ N ≤ 106)과 쿼리의 수 Q(1 ≤ Q ≤ 2 × 105)가 주어진다. 다음 Q개의 줄에 쿼리가 주어진다.
카드를 다 섞고 난 뒤 카드에 어떤 숫자가 적혀 있는지 위에서부터 순서대로 출력한다.
6 3 1 2 3 2 4 5 3 1 6
2 6 3 4 1 5
카드 6장이 있을 때 쿼리 3 1 6을 처리하면
1 2 3 4 5 6 ⇒ 1 4 2 5 3 6
이 되고, 카드 7장이 있을 때 3 1 7이 입력으로 들어오면
1 2 3 4 5 6 7 ⇒ 1 5 2 6 3 7 4
가 된다.