Submission #744650

#	Time	Username	Problem	Language	Result	Execution time	Memory
744650		oolimry	Archery (IOI09_archery)	C++17	50 / 100	2098 ms	30876 KiB

archery

#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;

///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]);

      if(it == available.begin()) it = --available.end();
      else it--;

      if(i == me) return *it;
      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();

    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;
        turnsleft %= n;

        //show2(turn, turnsleft);

        int res = (1-turnsleft+n) % n;
        if(res == 0) res = n;
        return res;
      }

      if(t < winner) swap(t, winner);

      candidates[turn+n].push_back(t);
    }
  }
}


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];

  int bestPos = -1;
  int bestVal = n;

  for(int t = 1;t <= n;t++){
    int res = solve(t);
    //show2(t, res);
    if(res <= bestVal){
      bestVal = res;
      bestPos = t; 
    }
  }

  cout << bestPos;
}

Compilation message (stderr)

archery.cpp: In function 'int solve(int)':
archery.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

• Subtask 1: 6 / 6
• Subtask 2: 44 / 94