Submission #745393

#TimeUsernameProblemLanguageResultExecution timeMemory
745393oolimryArchery (IOI09_archery)C++17
96 / 100
2065 ms41088 KiB
#include <bits/stdc++.h> using namespace std; #define sz(x) (int) (x).size() #define all(x) (x).begin(), (x).end() #define show(x) cerr << #x << " is " << x << endl; #define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl; #define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl; typedef long long lint; typedef pair<lint,lint> ii; int arr[400005]; int target[400005]; int n, R; int me; inline int bruhmod(int x){ int res = x%n; if(res <= 0) res += n; return res; } ///for strong vector<int> candidates[800005]; inline int solve(int s){ //return debuggingstuff[s]; target[me] = s; for(int i = 1;i <= 2*n;i++){ int newi = i + (i >= 2*s); target[arr[i]] = (newi+1)/2; } if(me >= n+2){ ///weak set<int> available; for(int i = 2;i <= n;i++) available.insert(i); for(int i = 2*n;i >= me;i--){ auto it = available.upper_bound(target[i]); bool looparound = false; if(it == available.begin()){ it = --available.end(); looparound = true; } else it--; if(i == me) return *it - (looparound * n); available.erase(it); } } else{ ///strong for(int i = 1;i <= 3*n;i++) candidates[i].clear(); for(int i = 1;i <= 2*n;i++){ candidates[target[i]].push_back((i > me) + (i >= me)); } if(candidates[1][0] < candidates[1][1]) swap(candidates[1][0], candidates[1][1]); int winner = candidates[1][1]; candidates[1].pop_back(); int looparounds = 0; vector<int> choices = {0,0,0}; for(int turn = 1;turn <= 3*n;turn++){ for(int x : candidates[turn]){ choices[x]++; } int t = 0; while(choices[t] == 0) t++; choices[t]--; if(turn >= 2*n and t == 1){ int turnsleft = R-turn+1; looparounds += (turnsleft + n - 1) / n; turnsleft %= n; int res = (1-turnsleft+n) % n; if(res == 0) res = n; return res - n * looparounds; } if(t < winner) swap(t, winner); if(t == 1) looparounds++; if(turn < 2*n) candidates[turn+n].push_back(t); } } assert(false); return -4; } inline int bsta(int x){ ///find last position <= x int low = 0, high = n+1; while(low < high-1){ int mid = (low+high)/2; if(solve(mid) <= x) low = mid; else high = mid; } return low; } int bestPos = -1; int bestVal = 1; inline void consider(int pos){ int val = solve(pos); int valmod = bruhmod(val); if(valmod < bestVal){ bestVal = valmod; bestPos = pos; } if(valmod == bestVal and bestPos < pos){ bestVal = valmod; bestPos = pos; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> R; cin >> me; //for(int i = 1;i <= n;i++) cin >> debuggingstuff[i]; if(me == 1){ cout << n; return 0; } for(int i = 1;i <= 2*n-1;i++) cin >> arr[i]; //solve(1); return 0; //for(int i = 1;i <= n;i++) show(solve(i)); bestVal = n+1; int small = solve(1); consider(1); consider(n); int pos = bsta(small); consider(pos); small += (n - bruhmod(small)); for(int x = 0;x < 1;x++){ int pos = bsta(small); if(pos >= n) break; pos++; int val = solve(pos); pos = bsta(val); consider(pos); small += n; } cout << bestPos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...