RiseOJ – 스왑 또 스왑 또 스왑

설명

농부 존의 소 $$N$$ 마리( $1\le N\le 10^5$ )가 한 줄로 서 있다. 왼쪽에서 $$i$$ 번째 소는 각 $1\le i\le N$ 에 대해 번호 $$i$$ 를 가지고 있다.

농부 존은 소들을 위한 새로운 아침 운동 루틴을 고안했다. 그는 소들에게 $$M$$ 개의 정수 쌍 $(L_1,R_1) \ldots (L_M, R_M)$ 을 주었다. 여기서 $1 \leq M \leq 100$ 이다. 그다음 소들에게 다음 $$M$$ 단계 과정을 정확히 $$K$$ 번( $1\le K\le 10^9$ ) 반복하라고 지시한다.

$$1$$ 부터 $$M$$ 까지의 각 $$i$$ 에 대해: 현재 왼쪽에서 위치 $L_i \ldots R_i$ 에 있는 소들의 수열이 순서를 뒤집는다.

소들이 이 과정을 정확히 $$K$$ 번 반복한 후, 각 $1\le i\le N$ 에 대해 왼쪽에서 $$i$$ 번째 소의 번호를 출력하시오.

문제 제공: Brian Dean

제약

배점

테스트 케이스 2는 $$N=K=100$$ 을 만족한다.
테스트 케이스 3-5는 $K\le 10^3$ 을 만족한다.
테스트 케이스 6-10은 추가 제약이 없다.

문제 제공: Brian Dean

입력 형식

첫째 줄에 $$N$$ , $$M$$ , $$K$$ 가 주어진다. 각 $1\le i\le M$ 에 대해, $$i+1$$ 번째 줄에 $$L_i$$ 와 $$R_i$$ 가 주어진다. 두 값 모두 $1 \ldots N$ 범위의 정수이며 $$L_i < R_i$$ 이다.

출력 형식

출력의 $$i$$ 번째 줄에, 명령 목록이 $$K$$ 번 수행된 후 배열의 $$i$$ 번째 원소를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 swap.in · 출력을 쓸 파일 swap.out

예제 1

입력

7 2 2
2 5
3 7

출력

설명

Initially, the order of the cows is $$[1,2,3,4,5,6,7]$$ from left to right. After
the first step of the process, the order is $$[1,5,4,3,2,6,7]$$ . After the second
step of the process, the order is $$[1,5,7,6,2,3,4]$$ . Repeating both steps a
second time yields the output of the sample.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > February > Silver

올림피아드 > USACO > 2019-2020 > February > Silver

태그

JudgeUSACO

스왑 또 스왑 또 스왑

평가 및 의견

풀이 제출