Submission #744665

#TimeUsernameProblemLanguageResultExecution timeMemory
744665oolimryArchery (IOI09_archery)C++17
84 / 100
2085 ms33100 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; int bruhmod(int x){ int res = x%n; if(res <= 0) res += n; return res; } ///for strong vector<int> candidates[600005]; int solve(int s){ target[me] = s; for(int i = 1;i <= 2*n;i++){ int newi = i + (i >= 2*s); target[arr[i]] = (newi+1)/2; } //for(int i = 1;i <= 2*n;i++) show2(i, target[i]); 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); } 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; priority_queue<int, vector<int>, greater<int> > choices; for(int turn = 1;turn <= 3*n+1;turn++){ for(int x : candidates[turn]) choices.push(x); int t = choices.top(); choices.pop(); if(turn > n and t == me){ 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 == me) looparounds++; candidates[turn+n].push_back(t); } } } 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; void consider(int pos){ int val = solve(pos); int valmod = bruhmod(val); //show3(valmod, bestVal, pos); if(valmod <= bestVal){ bestVal = valmod; bestPos = pos; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> R; cin >> me; if(me == 1){ cout << n; return 0; } for(int i = 1;i <= 2*n-1;i++) cin >> arr[i]; bestVal = n+1; int small = solve(1); consider(1); consider(n); small += (n - bruhmod(small)); for(int x = 0;x < 3;x++){ int pos = bsta(small); if(pos >= n) break; pos++; int val = solve(pos); pos = bsta(val); consider(pos); small += n; } cout << bestPos; }

Compilation message (stderr)

archery.cpp: In function 'int solve(int)':
archery.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...