DMPG '18 G1 - Musical Chairs

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int main(){
    6    ios::sync_with_stdio(0);
    7    cin.tie(0);
    8    int n, k;
    9    cin >> n >> k;
    10    vector<bool> empty(n + 1, false);
    11    for(int i = 0, x; i < k; i++){
    12        cin >> x;
    13        empty[x] = true;
    14 
    15    }
    16    vector<int> st(n + 1);
    17    for(int i = 1, x; i <= k + 1; i++){
    18        cin >> x;
    19        st[x] = i;
    20    }
    21    stack<int> stk;
    22    int emp = k, cur = 1;
    23    while(emp){
    24        if(st[cur]){
    25            stk.push(st[cur]);
    26            st[cur] = 0;
    27        }
    28        if(empty[cur] && !stk.empty()){
    29            empty[cur] = false;
    30            stk.pop();
    31            emp--;
    32        }
    33        cur = cur % n + 1;
    34    }
    35    cout << stk.top() << '\n';
    36    return 0;
    37}
    38