oj.uz

Submission #744662

# Submission time Handle Problem Language Result Execution time Memory
744662 2023-05-18T23:15:55 Z oolimry Archery (IOI09_archery) C++17
39 / 100
 2000 ms 35808 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;

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); if(valmod == 0) valmod = n;
	
	//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 += bruhmod(small);
	//show(small);
	//for(int t = 1;t <= n;t++) show2(t, solve(t));
	
	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

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

Subtask #1
5.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Incorrect 23 ms 14676 KB Output isn't correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 ms 14420 KB Output is correct

Subtask #2
34.0 / 94.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14424 KB Output isn't correct
2 Incorrect 9 ms 14420 KB Output isn't correct
3 Incorrect 18 ms 14548 KB Output isn't correct
4 Incorrect 158 ms 16376 KB Output isn't correct
5 Execution timed out 2056 ms 31788 KB Time limit exceeded
6 Correct 9 ms 14420 KB Output is correct
7 Incorrect 14 ms 14424 KB Output isn't correct
8 Incorrect 130 ms 16364 KB Output isn't correct
9 Correct 184 ms 16820 KB Output is correct
10 Incorrect 15 ms 14548 KB Output isn't correct
11 Incorrect 200 ms 17256 KB Output isn't correct
12 Incorrect 26 ms 14688 KB Output isn't correct
13 Correct 1959 ms 30316 KB Output is correct
14 Incorrect 41 ms 14992 KB Output isn't correct
15 Incorrect 304 ms 18488 KB Output isn't correct
16 Correct 9 ms 14408 KB Output is correct
17 Incorrect 16 ms 14548 KB Output isn't correct
18 Correct 17 ms 14668 KB Output is correct
19 Correct 28 ms 14728 KB Output is correct
20 Correct 40 ms 14980 KB Output is correct
21 Incorrect 89 ms 17188 KB Output isn't correct
22 Correct 254 ms 17644 KB Output is correct
23 Execution timed out 2037 ms 35808 KB Time limit exceeded
24 Correct 11 ms 14412 KB Output is correct
25 Correct 17 ms 14420 KB Output is correct
26 Incorrect 41 ms 14696 KB Output isn't correct
27 Correct 230 ms 15964 KB Output is correct
28 Execution timed out 2023 ms 23752 KB Time limit exceeded
29 Incorrect 17 ms 14420 KB Output isn't correct
30 Incorrect 37 ms 14776 KB Output isn't correct
31 Correct 241 ms 15880 KB Output is correct
32 Execution timed out 2049 ms 26592 KB Time limit exceeded
33 Incorrect 9 ms 14424 KB Output isn't correct
34 Correct 9 ms 14420 KB Output is correct
35 Incorrect 20 ms 14580 KB Output isn't correct
36 Incorrect 23 ms 14496 KB Output isn't correct
37 Incorrect 213 ms 15664 KB Output isn't correct
38 Incorrect 314 ms 16248 KB Output isn't correct
39 Correct 9 ms 14424 KB Output is correct
40 Incorrect 12 ms 14420 KB Output isn't correct
41 Correct 23 ms 14560 KB Output is correct
42 Incorrect 27 ms 14548 KB Output isn't correct
43 Correct 51 ms 14764 KB Output is correct
44 Incorrect 100 ms 15144 KB Output isn't correct
45 Incorrect 198 ms 15880 KB Output isn't correct
46 Correct 307 ms 16028 KB Output is correct
47 Execution timed out 2039 ms 28204 KB Time limit exceeded