oj.uz

Submission #744650

# Submission time Handle Problem Language Result Execution time Memory
744650 2023-05-18T22:23:12 Z oolimry Archery (IOI09_archery) C++17
50 / 100
 2000 ms 30876 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14536 KB Output is correct
4 Correct 770 ms 14696 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 13 ms 14420 KB Output is correct

Subtask #2
44.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 12 ms 14444 KB Output is correct
3 Correct 270 ms 14560 KB Output is correct
4 Execution timed out 2079 ms 15756 KB Time limit exceeded
5 Execution timed out 2083 ms 29628 KB Time limit exceeded
6 Correct 10 ms 14420 KB Output is correct
7 Correct 99 ms 14484 KB Output is correct
8 Execution timed out 2098 ms 15732 KB Time limit exceeded
9 Execution timed out 2057 ms 16432 KB Time limit exceeded
10 Correct 169 ms 14536 KB Output is correct
11 Execution timed out 2055 ms 16384 KB Time limit exceeded
12 Correct 1140 ms 14880 KB Output is correct
13 Execution timed out 2058 ms 25800 KB Time limit exceeded
14 Execution timed out 2074 ms 15244 KB Time limit exceeded
15 Execution timed out 2074 ms 17700 KB Time limit exceeded
16 Correct 12 ms 14420 KB Output is correct
17 Correct 227 ms 14548 KB Output is correct
18 Correct 534 ms 14624 KB Output is correct
19 Correct 1661 ms 14824 KB Output is correct
20 Execution timed out 2069 ms 15232 KB Time limit exceeded
21 Execution timed out 2077 ms 16924 KB Time limit exceeded
22 Execution timed out 2045 ms 17584 KB Time limit exceeded
23 Execution timed out 2059 ms 30876 KB Time limit exceeded
24 Correct 12 ms 14420 KB Output is correct
25 Correct 132 ms 14420 KB Output is correct
26 Execution timed out 2075 ms 14676 KB Time limit exceeded
27 Execution timed out 2061 ms 15972 KB Time limit exceeded
28 Execution timed out 2067 ms 22844 KB Time limit exceeded
29 Correct 273 ms 14516 KB Output is correct
30 Execution timed out 2060 ms 14748 KB Time limit exceeded
31 Execution timed out 2067 ms 15800 KB Time limit exceeded
32 Execution timed out 2064 ms 25844 KB Time limit exceeded
33 Correct 13 ms 14352 KB Output is correct
34 Correct 11 ms 14420 KB Output is correct
35 Correct 613 ms 14560 KB Output is correct
36 Correct 899 ms 14588 KB Output is correct
37 Execution timed out 2032 ms 15572 KB Time limit exceeded
38 Execution timed out 2070 ms 16212 KB Time limit exceeded
39 Correct 13 ms 14340 KB Output is correct
40 Correct 155 ms 14488 KB Output is correct
41 Correct 603 ms 14556 KB Output is correct
42 Correct 820 ms 14580 KB Output is correct
43 Execution timed out 2076 ms 14676 KB Time limit exceeded
44 Execution timed out 2073 ms 15056 KB Time limit exceeded
45 Execution timed out 2069 ms 15828 KB Time limit exceeded
46 Execution timed out 2068 ms 15956 KB Time limit exceeded
47 Execution timed out 2073 ms 27316 KB Time limit exceeded