fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 31492 (C++) Team selection
최초 업로드: 2025-10-30 23:43:43
최근 수정 시간: 2025-10-31 03:50:17
게시자: rlatjwls3333
카테고리: 백준
조회수: 9
# [Platinum V] Team selection [문제 링크](https://www.acmicpc.net/problem/31492) ## 문제 설명 <p>Two team leaders get to assemble their teams by choosing team members among a set of players that are numbered from $1$ to $N$. The leaders take turns, each picking the $k$<sup>th</sup> player among the remaining ones, according to their ideas of which one of the remaining players would be the best addition to their teams.</p> <p>Given the choices of the two leaders (the first team leader starts first), please compute the list of players in each team.</p> ## 입력 <p>The input consists of three lines. The first line contains the single integer $N$. The second line contains $N/2$ space-separated integers $a_1, a_2, \dots , a_{N/2}$ representing the choices of the first team leader: during the $(2k - 1)$<sup>th</sup> turn, the first leader chose the $a_k$<sup>th</sup> remaining player. The third line contains $N/2$ space-separated integers $b_1, b_2, \dots , b_{N/2}$ representing the choices of the second team leader: during the $2k$<sup>th</sup> turn, the second leader chose the $b_k$<sup>th</sup> remaining player.</p> ## 출력 <p>The output should contain two lines, each containing $N/2$ space-separated integers. The first line should contain the list $x_1, x_2, \dots , x_{N/2}$ of the players chosen to become members of the first team, in the order they were chosen: the player $x_k$ was chosen during the $(2k - 1)$<sup>th</sup> turn. The second line should contain the list $y_1, y_2, \dots , y_{N/2}$ of the players chosen to become members of the second team, in the order they were chosen: the player $y_k$ was chosen during the $2k$<sup>th</sup> turn.</p> ## 풀이 세그 워크를 구현하여 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 4'000'001; int a[MAX], _size=1, arr[MAX*4]; void update(int x) { arr[x]=0; while(x>1) { x>>=1; arr[x] = arr[x*2]+arr[x*2+1]; } } int search(int val, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) { if(nodeL==nodeR) { update(nodeNum); return nodeL+1; } int mid = nodeL+nodeR>>1; if(val<=arr[nodeNum*2]) return search(val, nodeNum*2, nodeL, mid); return search(val-arr[nodeNum*2], nodeNum*2+1, mid+1, nodeR); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(_size<n) _size<<=1; _size<<=1; for(int i=0;i<n;i++) arr[i+_size/2]=1; for(int i=_size/2-1;i>0;i--) arr[i] = arr[i*2]+arr[i*2+1]; for(int i=0;i<n;i+=2) cin >> a[i]; for(int i=1;i<n;i+=2) cin >> a[i]; vector<int> res1, res2; for(int i=0;i<n;i++) { if(i%2==0) res1.push_back(search(a[i])); else res2.push_back(search(a[i])); } for(int e:res1) cout << e << ' '; cout << '\n'; for(int e:res2) cout << e << ' '; } ```