# [Platinum V] 카드 게임 [문제 링크](https://www.acmicpc.net/problem/16566) ## 문제 설명 <p>철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.</p> <ol> <li>N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.</li> <li>N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.</li> <li>철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.</li> <li>철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.</li> </ol> <p>철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.</p> <p>민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.</p> <p>K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.</p> ## 입력 <p>첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))</p> <p>다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.</p> <p>다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.</p> ## 출력 <p>K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.</p> ## 풀이 #### 분리집합을 이용해 가지고있지 않거나, 이미 사용한 카드는 그 숫자보다 큰 카드로 합치는 형태로 구현하였다. 찾아야 하는 숫자가 입력된 숫자보다 큰 숫자여서 흔히 알려진 구현과는 반대로, parent[x]에 x+1을 집어넣었다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 4'000'002; int parent[MAX]; int _find(int x) { if(parent[x]==x) return x; return parent[x] = _find(parent[x]); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for(int i=1;i<=n;i++) parent[i]=i+1; while(m--) { int num; cin >> num; parent[num] = num; } while(k--) { int num; cin >> num; int val = _find(num+1); parent[val] = val+1; cout << val << '\n'; } } ```