Submission #745402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745402	2023-05-20T01:30:50 Z	oolimry	Archery (IOI09_archery)	C++17	100 / 100	1638 ms	39116 KB

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;

inline int bruhmod(int x){
	int res = x%n;
	if(res <= 0) res += n;
	return res;
}

///for strong
vector<int> candidates[800005];

///for weak
int taken[200005];

inline int solve(int s){
	//return debuggingstuff[s];
	target[me] = s;
	for(int i = 1;i <= 2*n;i++){
		int newi = i + (i >= 2*s);
		target[arr[i]] = (newi+1)/2;
	}
	
	
	if(me >= n+2){ ///weak
		fill(taken,taken+n+1,0);
		
		for(int i = me+1;i <= 2*n;i++) taken[target[i]]++;
		
		int cnt = 0;
		for(int i = n;i >= 2;i--){
			cnt += taken[i]; taken[i] = 0;
			if(cnt > 0){
				taken[i] = 1;
				cnt--;
			}
		}
		cnt += taken[1];
		for(int i = n;i >= 2;i--){
			cnt += taken[i]; taken[i] = 0;
			if(cnt > 0){
				taken[i] = 1;
				cnt--;
			}
		}
		
		bool looparound = false;
		int pos = target[me];
		while(true){
			if(pos == 1){
				pos = n;
				looparound = true;
			}
			if(taken[pos] == 0) return pos - (looparound * n);
			
			pos--;
		}
	}
	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 > me) + (i >= me));
		}
		
		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;
		
		vector<int> choices = {0,0,0};
		for(int turn = 1;turn <= 3*n;turn++){
			for(int x : candidates[turn]){
				choices[x]++;
			}
			
			int t = 0;
			while(choices[t] == 0) t++;
			choices[t]--;
			
			if(turn >= 2*n and t == 1){
				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 == 1) looparounds++;
			
			if(turn < 2*n) candidates[turn+n].push_back(t);
		}
	}
	assert(false);
	return -4;
}

inline 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;
inline void consider(int pos){
	int val = solve(pos);
	int valmod = bruhmod(val); 
		
	if(valmod < bestVal){
		bestVal = valmod;
		bestPos = pos;
	}
	if(valmod == bestVal and bestPos < pos){
		bestVal = valmod;
		bestPos = pos;
	}
}

signed main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> R;
	cin >> me;
	
	//for(int i = 1;i <= n;i++) cin >> debuggingstuff[i];
	
	if(me == 1){
		cout << n;
		return 0;
	}
	
	for(int i = 1;i <= 2*n-1;i++) cin >> arr[i];	
	
	
	//solve(1); return 0;
	//for(int i = 1;i <= n;i++) show(solve(i));
	
	bestVal = n+1;
	int small = solve(1);
	consider(1); consider(n);
	
	int pos = bsta(small);
	consider(pos);
	
	small += (n - bruhmod(small));
	
	for(int x = 0;x < 1;x++){
		int pos = bsta(small);
		if(pos >= n) break;
		
		pos++;
		int val = solve(pos);
		pos = bsta(val);
		consider(pos);
		
		small += n;
	}
	
	cout << bestPos;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	19028 KB	Output is correct
2	Correct	11 ms	19136 KB	Output is correct
3	Correct	11 ms	19124 KB	Output is correct
4	Correct	17 ms	19368 KB	Output is correct
5	Correct	11 ms	19028 KB	Output is correct
6	Correct	12 ms	19040 KB	Output is correct

Subtask #2

94.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	19128 KB	Output is correct
2	Correct	11 ms	19120 KB	Output is correct
3	Correct	13 ms	19284 KB	Output is correct
4	Correct	64 ms	20956 KB	Output is correct
5	Correct	1638 ms	38016 KB	Output is correct
6	Correct	13 ms	19028 KB	Output is correct
7	Correct	12 ms	19132 KB	Output is correct
8	Correct	49 ms	20940 KB	Output is correct
9	Correct	89 ms	21708 KB	Output is correct
10	Correct	13 ms	19156 KB	Output is correct
11	Correct	90 ms	21708 KB	Output is correct
12	Correct	17 ms	19396 KB	Output is correct
13	Correct	923 ms	33060 KB	Output is correct
14	Correct	24 ms	19668 KB	Output is correct
15	Correct	149 ms	22784 KB	Output is correct
16	Correct	11 ms	19112 KB	Output is correct
17	Correct	15 ms	19156 KB	Output is correct
18	Correct	16 ms	19260 KB	Output is correct
19	Correct	19 ms	19520 KB	Output is correct
20	Correct	26 ms	19724 KB	Output is correct
21	Correct	91 ms	21644 KB	Output is correct
22	Correct	121 ms	22612 KB	Output is correct
23	Correct	1586 ms	39116 KB	Output is correct
24	Correct	11 ms	19028 KB	Output is correct
25	Correct	12 ms	19152 KB	Output is correct
26	Correct	14 ms	19204 KB	Output is correct
27	Correct	27 ms	19680 KB	Output is correct
28	Correct	128 ms	21760 KB	Output is correct
29	Correct	12 ms	19156 KB	Output is correct
30	Correct	13 ms	19156 KB	Output is correct
31	Correct	22 ms	19736 KB	Output is correct
32	Correct	160 ms	22732 KB	Output is correct
33	Correct	11 ms	19028 KB	Output is correct
34	Correct	11 ms	19028 KB	Output is correct
35	Correct	12 ms	19136 KB	Output is correct
36	Correct	12 ms	19156 KB	Output is correct
37	Correct	21 ms	19652 KB	Output is correct
38	Correct	26 ms	19748 KB	Output is correct
39	Correct	10 ms	19012 KB	Output is correct
40	Correct	12 ms	19156 KB	Output is correct
41	Correct	14 ms	19172 KB	Output is correct
42	Correct	14 ms	19108 KB	Output is correct
43	Correct	15 ms	19156 KB	Output is correct
44	Correct	20 ms	19380 KB	Output is correct
45	Correct	25 ms	19732 KB	Output is correct
46	Correct	29 ms	19768 KB	Output is correct
47	Correct	162 ms	23292 KB	Output is correct