oj.uz

Submission #744653

# Submission time Handle Problem Language Result Execution time Memory
744653 2023-05-18T22:25:30 Z oolimry Archery (IOI09_archery) C++17
50 / 100
 2000 ms 29140 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]);
			
			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;
				turnsleft %= n;
								
				int res = (1-turnsleft+n) % n;
				if(res == 0) res = n;
				return res;
			}
			
			if(t < winner) swap(t, winner);
			if(t == me) looparounds++;
			
			candidates[turn+n].push_back(t);
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> R;
	cin >> me;
	assert(n <= 5000);
	
	if(me == 1){
		cout << n;
		return 0;
	}
	
	for(int i = 1;i <= 2*n-1;i++) cin >> arr[i];
	
	//show(solve(3));
	//return 0;
	
	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:80:1: warning: control reaches end of non-void function [-Wreturn-type]
   80 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 7 ms 14396 KB Output is correct
3 Correct 9 ms 14396 KB Output is correct
4 Correct 793 ms 14828 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 13 ms 14328 KB Output is correct

Subtask #2
44.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14312 KB Output is correct
2 Correct 13 ms 14460 KB Output is correct
3 Correct 278 ms 14824 KB Output is correct
4 Runtime error 18 ms 29140 KB Execution killed with signal 6
5 Runtime error 18 ms 29004 KB Execution killed with signal 6
6 Correct 12 ms 14400 KB Output is correct
7 Correct 106 ms 14536 KB Output is correct
8 Runtime error 18 ms 29080 KB Execution killed with signal 6
9 Runtime error 20 ms 29012 KB Execution killed with signal 6
10 Correct 176 ms 14680 KB Output is correct
11 Runtime error 18 ms 29012 KB Execution killed with signal 6
12 Correct 1127 ms 14940 KB Output is correct
13 Runtime error 18 ms 29012 KB Execution killed with signal 6
14 Execution timed out 2078 ms 15360 KB Time limit exceeded
15 Runtime error 21 ms 29012 KB Execution killed with signal 6
16 Correct 13 ms 14428 KB Output is correct
17 Correct 232 ms 14792 KB Output is correct
18 Correct 521 ms 14672 KB Output is correct
19 Correct 1643 ms 15052 KB Output is correct
20 Execution timed out 2088 ms 15196 KB Time limit exceeded
21 Runtime error 19 ms 29004 KB Execution killed with signal 6
22 Runtime error 22 ms 28956 KB Execution killed with signal 6
23 Runtime error 19 ms 29012 KB Execution killed with signal 6
24 Correct 14 ms 14420 KB Output is correct
25 Correct 143 ms 14480 KB Output is correct
26 Execution timed out 2086 ms 15036 KB Time limit exceeded
27 Runtime error 19 ms 29012 KB Execution killed with signal 6
28 Runtime error 19 ms 28984 KB Execution killed with signal 6
29 Correct 270 ms 14532 KB Output is correct
30 Execution timed out 2071 ms 15148 KB Time limit exceeded
31 Runtime error 21 ms 28988 KB Execution killed with signal 6
32 Runtime error 21 ms 29012 KB Execution killed with signal 6
33 Correct 13 ms 14420 KB Output is correct
34 Correct 14 ms 14420 KB Output is correct
35 Correct 574 ms 14676 KB Output is correct
36 Correct 871 ms 15068 KB Output is correct
37 Runtime error 21 ms 28972 KB Execution killed with signal 6
38 Runtime error 21 ms 29020 KB Execution killed with signal 6
39 Correct 13 ms 14420 KB Output is correct
40 Correct 143 ms 14480 KB Output is correct
41 Correct 616 ms 14796 KB Output is correct
42 Correct 800 ms 14700 KB Output is correct
43 Execution timed out 2084 ms 14892 KB Time limit exceeded
44 Runtime error 19 ms 29012 KB Execution killed with signal 6
45 Runtime error 18 ms 29000 KB Execution killed with signal 6
46 Runtime error 19 ms 29012 KB Execution killed with signal 6
47 Runtime error 19 ms 29096 KB Execution killed with signal 6