Submission #744681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744681	2023-05-19T01:01:45 Z	oolimry	Archery (IOI09_archery)	C++17	88 / 100	2000 ms	32992 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 < 2;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	9 ms	14412 KB	Output is correct
3	Correct	8 ms	14420 KB	Output is correct
4	Correct	26 ms	14712 KB	Output is correct
5	Correct	9 ms	14496 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct

Subtask #2

82.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14424 KB	Output is correct
2	Correct	8 ms	14420 KB	Output is correct
3	Correct	18 ms	14568 KB	Output is correct
4	Correct	174 ms	16212 KB	Output is correct
5	Execution timed out	2072 ms	30924 KB	Time limit exceeded
6	Correct	8 ms	14420 KB	Output is correct
7	Correct	13 ms	14504 KB	Output is correct
8	Correct	93 ms	16212 KB	Output is correct
9	Correct	234 ms	16796 KB	Output is correct
10	Correct	12 ms	14548 KB	Output is correct
11	Correct	256 ms	16960 KB	Output is correct
12	Correct	30 ms	14748 KB	Output is correct
13	Execution timed out	2068 ms	29084 KB	Time limit exceeded
14	Correct	54 ms	15020 KB	Output is correct
15	Correct	404 ms	18156 KB	Output is correct
16	Correct	8 ms	14420 KB	Output is correct
17	Correct	18 ms	14580 KB	Output is correct
18	Correct	21 ms	14548 KB	Output is correct
19	Correct	35 ms	14792 KB	Output is correct
20	Correct	50 ms	14940 KB	Output is correct
21	Correct	263 ms	16948 KB	Output is correct
22	Correct	341 ms	17396 KB	Output is correct
23	Execution timed out	2083 ms	32992 KB	Time limit exceeded
24	Correct	10 ms	14436 KB	Output is correct
25	Correct	15 ms	14480 KB	Output is correct
26	Correct	49 ms	14676 KB	Output is correct
27	Correct	287 ms	15732 KB	Output is correct
28	Execution timed out	2081 ms	22300 KB	Time limit exceeded
29	Correct	16 ms	14420 KB	Output is correct
30	Correct	43 ms	14676 KB	Output is correct
31	Correct	310 ms	15652 KB	Output is correct
32	Execution timed out	2074 ms	25344 KB	Time limit exceeded
33	Correct	8 ms	14420 KB	Output is correct
34	Correct	8 ms	14420 KB	Output is correct
35	Correct	22 ms	14560 KB	Output is correct
36	Correct	27 ms	14528 KB	Output is correct
37	Correct	255 ms	15464 KB	Output is correct
38	Correct	395 ms	15960 KB	Output is correct
39	Correct	8 ms	14420 KB	Output is correct
40	Correct	14 ms	14420 KB	Output is correct
41	Correct	23 ms	14552 KB	Output is correct
42	Correct	26 ms	14444 KB	Output is correct
43	Correct	60 ms	14676 KB	Output is correct
44	Correct	105 ms	15040 KB	Output is correct
45	Correct	236 ms	15656 KB	Output is correct
46	Correct	373 ms	15784 KB	Output is correct
47	Execution timed out	2033 ms	26828 KB	Time limit exceeded