# [Platinum III] Jungle Game [문제 링크](https://www.acmicpc.net/problem/32558) ## 문제 설명 <p>Denise is designing a rainforest themed board game. The goal of the game is for each player to form a team of two characters and complete various challenges.</p> <p>There are $N$ different characters numbered from $1$ to $N$. Each character $i$ has two attributes $p_i$ and $s_i$ (problem solving skill and strength). The numbers $p_i$ and $s_i$ are positive integers satisfying $1 \leq p_i, s_i \leq N$. Before the game starts, each player will pick two characters $i$ and $j$ to form a team. It is possible to pick two copies of the same character. The total problem solving skill and strength of the team will be $p_i + p_j$ and $s_i + s_j$ respectively. </p> <p>In the game there are also $N$ challenge cards numbered from $1$ to $N$. Each of these also has two attributes $P_k$ and $S_k$. Denise has already designed the challenge cards and decided on the values of all numbers $P_1, P_2, \dots, P_N$ and $S_1, S_2, \dots, S_N$. However, the rules of the game assume that it is not possible for a player to form a team whose problem solving skill and strength are both the same as one of the challenge cards. In other words, the situation </p> <p>$$p_i+p_j = P_k \text{ and } s_i+s_j = S_k$$</p> <p>should never occur for any triple $i,j,k$ (note that $i$ can be equal to $j$).</p> <p>The only thing left to do is to decide the $N$ distinct pairs $(p_1, s_1), (p_2, s_2) \dots, (p_N, s_N)$ such that $1 \leq p_i, s_i \leq N$ and the situation above never happens.</p> ## 입력 <p>The first line contains the integer $N$ ($1 \leq N \leq 2000$).</p> <p>The following $N$ lines contain the values of the challenge cards $P_i, S_i$ ($1 \leq P_i, S_i \leq 2 \cdot N$).</p> ## 출력 <p>If there is no solution, print "NO". Otherwise, print "YES" followed by $N$ lines, each containing a pair of integers $p_i, s_i$ ($1 \leq p_i, s_i \leq N$). These pairs of integers must be distinct. In other words, you may not have two indices $i \neq j$ with $p_i = p_j$ and $s_i = s_j$.</p> ## 풀이 N이 2000이 아니라 20000 정도로 들어오는 것 같습니다. - 홀수가 하나라도 등장하거나 중복된 짝수가 나온다면 비어있는 짝수 구간이 존재할 것이기에 그 짝수 구간을 출력하면 된다. - 만약 전부 중복되지 않은 짝수라면, 뒤가 2N인 쌍의 앞쪽을 고정시켜놓고, 뒤를 1~N-1까지 N-1개와 앞쪽이 홀+짝인 적당한 수 하나를 출력하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; bool exist1[20'001], exist2[20'001]; bool exist[20'001][20'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) { int x, y; cin >> x >> y; exist[x][y]=true; exist1[x]=true; exist2[y]=true; } if(n==1) { if(exist[2][2]) cout << "NO"; else cout << "YES\n1 1"; return 0; } cout << "YES\n"; for(int i=1;i<=n;i++) { if(!exist1[i*2]) { for(int j=1;j<=n;j++) cout << i << ' ' << j << '\n'; return 0; } } for(int i=1;i<=n;i++) { if(!exist2[i*2]) { for(int j=1;j<=n;j++) cout << j << ' ' << i << '\n'; return 0; } } for(int i=1;i<=n;i++) { if(exist[2*i][2*n]) { for(int j=1;j<n;j++) cout << i << ' ' << j << '\n'; if(i%2) { if(!exist[4][2]) cout << "2 1"; else cout << "2 2"; } else { if(!exist[2][2]) cout << "1 1"; else cout << "1 2"; } return 0; } } } ```