백준 31492 (C++) Team selection

최초 업로드: 2025-10-30 23:43:43

최근 수정 시간: 2025-10-31 03:50:17

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Team selection

[문제 링크](https://www.acmicpc.net/problem/31492)

## 문제 설명

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$th player among the remaining ones, according to their ideas of which one of the remaining players would be the best addition to their teams.

Given the choices of the two leaders (the first team leader starts first), please compute the list of players in each team.

## 입력

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)$th turn, the first leader chose the $a_k$th 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$th turn, the second leader chose the $b_k$th remaining player.

## 출력

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)$th 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$th turn.

## 풀이
세그 워크를 구현하여 풀었습니다.

``` 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 << ' ';
}
```