Submission #744682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744682	2023-05-19T01:02:56 Z	oolimry	Archery (IOI09_archery)	C++17	90 / 100	2000 ms	32996 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[600005];

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

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(){
	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];	
	
	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;
}

Compilation message

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

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14292 KB	Output is correct
2	Correct	8 ms	14292 KB	Output is correct
3	Correct	9 ms	14316 KB	Output is correct
4	Correct	23 ms	14632 KB	Output is correct
5	Correct	10 ms	14420 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct

Subtask #2

84.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14324 KB	Output is correct
2	Correct	11 ms	14420 KB	Output is correct
3	Correct	16 ms	14548 KB	Output is correct
4	Correct	132 ms	16208 KB	Output is correct
5	Execution timed out	2076 ms	30916 KB	Time limit exceeded
6	Correct	9 ms	14420 KB	Output is correct
7	Correct	11 ms	14420 KB	Output is correct
8	Correct	98 ms	16200 KB	Output is correct
9	Correct	197 ms	16724 KB	Output is correct
10	Correct	13 ms	14548 KB	Output is correct
11	Correct	227 ms	16692 KB	Output is correct
12	Correct	25 ms	14744 KB	Output is correct
13	Correct	1878 ms	29152 KB	Output is correct
14	Correct	47 ms	14932 KB	Output is correct
15	Correct	339 ms	17828 KB	Output is correct
16	Correct	9 ms	14444 KB	Output is correct
17	Correct	15 ms	14592 KB	Output is correct
18	Correct	19 ms	14596 KB	Output is correct
19	Correct	29 ms	14792 KB	Output is correct
20	Correct	45 ms	14960 KB	Output is correct
21	Correct	210 ms	16888 KB	Output is correct
22	Correct	276 ms	17308 KB	Output is correct
23	Execution timed out	2052 ms	32996 KB	Time limit exceeded
24	Correct	8 ms	14420 KB	Output is correct
25	Correct	14 ms	14488 KB	Output is correct
26	Correct	45 ms	14724 KB	Output is correct
27	Correct	231 ms	15724 KB	Output is correct
28	Execution timed out	2056 ms	22348 KB	Time limit exceeded
29	Correct	15 ms	14420 KB	Output is correct
30	Correct	38 ms	14720 KB	Output is correct
31	Correct	229 ms	15656 KB	Output is correct
32	Execution timed out	2061 ms	25240 KB	Time limit exceeded
33	Correct	9 ms	14420 KB	Output is correct
34	Correct	9 ms	14420 KB	Output is correct
35	Correct	20 ms	14560 KB	Output is correct
36	Correct	24 ms	14452 KB	Output is correct
37	Correct	212 ms	15472 KB	Output is correct
38	Correct	318 ms	15980 KB	Output is correct
39	Correct	12 ms	14420 KB	Output is correct
40	Correct	14 ms	14492 KB	Output is correct
41	Correct	21 ms	14548 KB	Output is correct
42	Correct	25 ms	14548 KB	Output is correct
43	Correct	47 ms	14720 KB	Output is correct
44	Correct	84 ms	14980 KB	Output is correct
45	Correct	177 ms	15660 KB	Output is correct
46	Correct	315 ms	15868 KB	Output is correct
47	Execution timed out	2066 ms	26872 KB	Time limit exceeded