페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5633

댄서 곰 (Rotate and Shift) 4s 32MB

문제

봄 맞이 축제에 N(1 \le N \le 2 \cdot 10^5 ) 마리의 곰들은 둥글게 서 있으면서 서로 순서를 바꾸는 새로운 춤을 만들었다.

구체적으로, N개의 자리가 원형으로 있으며 0번부터 N-1번까지 순서대로 번호 매겨져 있으며 N-1번 다음은 0번으로 이어지는 원형이다.

곰들 역시 번호가 매겨져 있으며 초기에는 i번째 자리에는 i번 곰이 서 있다.

여기에서 K개의 특정 자리(0=A_1 \lt A_2 \lt \ldots \lt A_K \lt N)는 "댄서 곰의 자리"로, 이 자리에 있는 곰은 다른 곳으로 움직인다. (1 \le K \le N)

신이 난 곰들은 춤을 추는 매 분마다 2가지 동작을 한다.

먼저, "댄서 곰의 자리"에 있는 곰이 회전 이동을 한다. 회전 이동의 과정은 다음과 같다.
A_1 자리에 있는 곰은 A_2 자리로 이동하고 A_2 자리에 있는 곰은 A_3 자리로 이동하는 식이며 최종적으로 A_K자리에 있는 곰은 A_1 자리로 이동한다.

(이러한 K번의 동작은 모두 동시에 발생하므로 회전 이동이 완료된 후에도 모든 "댄서 곰의 자리"에는 정확히 한 마리의 곰이 있다.)

다음 동작으로 "댄서 곰의 자리"를 변경한다. A_1은 A_1+1이 되고, A_2는 A_2+1이 된다. (A_i=N-1인 경우 A_i는 0이 된다.)

T분의 춤이 끝난 후 곰의 순서를 계산하라. (1 \le T \le 10^9)​


입력

첫 줄에 N, K, T가 주어진다.

다음 줄에 K개의 "댄서 곰의 자리" A_1,A_2,\ldots,A_K 가 주어진다. A_1=0과 A값은 증가하는 순서로 주어짐에 유의하라.


출력

T분의 춤이 끝난 후 0번 자리부터 N-1번 자리에 있는 곰의 번호를 공백을 구분으로 출력하라.


예제 

5 3 4

0 2 3
1 2 3 4 0

위 예제는 T분 동안의 곰의 순서와 A는 다음과 같다.  

초기 상태 T = 0: 순서 = [0 1 2 3 4], A = [0 2 3]

T = 1: 순서= [3 1 0 2 4]

T = 1: A = [1 3 4]

T = 2: 순서 = [3 4 0 1 2]

T = 2: A = [2 4 0]

T = 3: 순서 = [2 4 3 1 0]

T = 3: A = [3 0 1]

T = 4: 순서 = [1 2 3 4 0]​ 


출처

USACO 2023 US Open Bronze

로그인해야 코드를 작성할 수 있어요.