Submission #744678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744678	2023-05-19T00:48:09 Z	oolimry	Archery (IOI09_archery)	C++17	84 / 100	2000 ms	37592 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;
#define int long long


int debuggingstuff[400005];

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

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 < 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;
		
	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 += (n - bruhmod(small));
	
	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 'long long int solve(long long int)':
archery.cpp:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^

Subtask #1

6.0 / 6.0

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

Subtask #2

78.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14384 KB	Output is correct
2	Correct	9 ms	14536 KB	Output is correct
3	Correct	18 ms	14636 KB	Output is correct
4	Correct	139 ms	16568 KB	Output is correct
5	Execution timed out	2096 ms	34996 KB	Time limit exceeded
6	Correct	10 ms	14420 KB	Output is correct
7	Incorrect	9 ms	14548 KB	Output isn't correct
8	Incorrect	57 ms	16476 KB	Output isn't correct
9	Correct	189 ms	17316 KB	Output is correct
10	Incorrect	10 ms	14600 KB	Output isn't correct
11	Correct	212 ms	17508 KB	Output is correct
12	Correct	28 ms	14828 KB	Output is correct
13	Correct	1967 ms	32156 KB	Output is correct
14	Correct	45 ms	15060 KB	Output is correct
15	Correct	340 ms	18924 KB	Output is correct
16	Correct	10 ms	14420 KB	Output is correct
17	Correct	16 ms	14624 KB	Output is correct
18	Correct	19 ms	14696 KB	Output is correct
19	Correct	29 ms	14880 KB	Output is correct
20	Correct	38 ms	15120 KB	Output is correct
21	Correct	209 ms	17488 KB	Output is correct
22	Correct	247 ms	18156 KB	Output is correct
23	Execution timed out	2096 ms	37592 KB	Time limit exceeded
24	Correct	9 ms	14420 KB	Output is correct
25	Correct	12 ms	14420 KB	Output is correct
26	Correct	42 ms	14732 KB	Output is correct
27	Correct	217 ms	16060 KB	Output is correct
28	Execution timed out	2037 ms	24268 KB	Time limit exceeded
29	Correct	14 ms	14420 KB	Output is correct
30	Correct	34 ms	14756 KB	Output is correct
31	Correct	241 ms	15968 KB	Output is correct
32	Execution timed out	2065 ms	27980 KB	Time limit exceeded
33	Correct	9 ms	14420 KB	Output is correct
34	Correct	8 ms	14420 KB	Output is correct
35	Correct	19 ms	14548 KB	Output is correct
36	Correct	23 ms	14548 KB	Output is correct
37	Correct	194 ms	15740 KB	Output is correct
38	Correct	297 ms	16356 KB	Output is correct
39	Correct	11 ms	14420 KB	Output is correct
40	Correct	12 ms	14420 KB	Output is correct
41	Correct	20 ms	14548 KB	Output is correct
42	Correct	22 ms	14600 KB	Output is correct
43	Correct	47 ms	14804 KB	Output is correct
44	Correct	86 ms	15192 KB	Output is correct
45	Correct	175 ms	15956 KB	Output is correct
46	Correct	283 ms	16128 KB	Output is correct
47	Execution timed out	2075 ms	30040 KB	Time limit exceeded