20315번 - 야바위 서브태스크출처다국어분류
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 43 | 16 | 13 | 35.135% |
문제
윤이는 야바위 게임에 참가하려고 한다. 야바위 게임의 규칙은 다음과 같다. 먼저 진행자는 $K$개의 컵을 일렬로 뒤집어 놓고, 참가자 앞에서 컵 하나에 구슬을 담는다. 진행자가 컵을 섞는 동작을 하면 참가자는 진행자의 동작을 잘 보고 구슬의 최종 위치를 맞혀야 한다.
진행자의 동작은 두 종류가 있다. 첫 번째는 두 컵의 위치를 바꾸는 것이다. 두 번째는 한 컵에 있는 내용물을 다른 컵으로 옮기는 것이다. 진행자는 두 가지 동작을 잘 섞어서 $N$번의 동작을 했다.
윤이는 눈이 빨라서 진행자가 어떤 동작을 하는지 전부 기억했다. 하지만 윤이는 의외의 허당이라서 진행자의 동작 하나를 놓치고 말았다. 심지어 처음에 구슬이 담겨 있던 컵의 위치마저 까먹었다. 쿼리마다 윤이가 놓친 정보들이 주어졌을 때 구슬의 최종 위치를 찾는 프로그램을 작성하시오.
입력
첫 줄에 컵의 개수 $K$, 진행자가 수행한 동작의 수 $N$과 쿼리의 수 $M$이 주어진다.
다음 $N-1$개 줄에 윤이가 본 동작을 나타내는 정수 $t,a,b$가 순서대로 주어진다. $(t\in\{1,2\}, 1\le a,b\le K, a\ne b)$
- $t=1$이면 $a$번째에 위치한 컵과 $b$번째에 위치한 컵의 위치를 바꾸는 동작을 나타낸다.
- $t=2$이면 $a$번째에 위치한 컵의 내용물을 $b$번째에 위치한 컵으로 옮기는 동작을 나타낸다.
다음 $M$개 줄에 쿼리가 주어진다. 각 쿼리마다 정수 $s, m, t, a, b$가 주어진다.
- $s$는 처음에 구슬이 담겨 있던 컵의 위치이다. $(1\le s\le K)$
- $m$은 윤이가 놓친 동작이 몇 번째인지를 나타낸다. $(1\le m \le N)$
- $t, a, b$는 윤이가 놓친 동작을 나타내며, 어떤 동작을 나타내는지는 위에서 설명한 것과 동일하다.
출력
각 줄에 쿼리마다 최종적으로 구슬이 담긴 컵이 몇 번째인지 출력한다.
제한
$2 ≤ K,N,M ≤ 300,000$
서브태스크 1 (50점)
윤이가 본 야바위꾼의 동작 $N-1$개가 $t=1$인 경우만 주어진다. 윤이가 놓친 동작은 $t=1,2$ 모두 가능하다.
서브태스크 2 (130점)
추가적인 제약 조건이 없다.
예제 입력 1
5 5 4 1 3 2 2 5 2 1 2 4 2 1 3 5 4 1 4 1 3 1 1 1 3 3 2 2 3 2 4 5 2 2 5
예제 출력 1
3 3 4 5
첫 번째 쿼리의 경우 구슬은 처음에 $5$번째 컵에 담겨 있다. 구슬의 위치는 다음과 같이 변한다.
- $3$번째와 $2$번째 컵의 위치를 바꾼다. 구슬은 그대로 $5$번째 컵에 있다.
- $5$번째 컵의 내용물을 $2$번째 컵으로 옮긴다. 구슬은 $2$번째 컵으로 옮겨간다.
- $2$번째와 $4$번째 컵의 위치를 바꾼다. 구슬은 $4$번째 컵으로 옮겨간다.
- 윤이가 놓친 $4$번째 동작이다. $4$번째 컵과 $1$번째 컵의 위치를 바꾼다. 구슬은 $1$번째 컵으로 옮겨간다.
- $1$번째 컵의 내용물을 $3$번째 컵으로 옮긴다. 구슬은 $3$번째 컵으로 옮겨간다.
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2021 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
