oj.uz

Submission #744783

# Submission time Handle Problem Language Result Execution time Memory
744783 2023-05-19T05:40:15 Z oolimry Archery (IOI09_archery) C++17
86 / 100
 2000 ms 65536 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;

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;
	}
	
	
	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 < 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 = 2;
			while(choices[t] == 0) t--;
			choices[t]--;
			
			//show(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++;
			
			candidates[turn+n].push_back(t);
		}
	}
	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 7 ms 14292 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 15 ms 14884 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct

Subtask #2
80.0 / 94.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 12 ms 14804 KB Output is correct
4 Correct 68 ms 17504 KB Output is correct
5 Correct 1614 ms 36816 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Incorrect 9 ms 14548 KB Output isn't correct
8 Incorrect 65 ms 16692 KB Output isn't correct
9 Correct 87 ms 18396 KB Output is correct
10 Incorrect 10 ms 14548 KB Output isn't correct
11 Correct 93 ms 19148 KB Output is correct
12 Correct 15 ms 15064 KB Output is correct
13 Correct 928 ms 51272 KB Output is correct
14 Correct 24 ms 15556 KB Output is correct
15 Correct 162 ms 23456 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 11 ms 14804 KB Output is correct
18 Correct 13 ms 14772 KB Output is correct
19 Correct 17 ms 15316 KB Output is correct
20 Correct 22 ms 15248 KB Output is correct
21 Correct 87 ms 18876 KB Output is correct
22 Correct 134 ms 20088 KB Output is correct
23 Runtime error 202 ms 65536 KB Execution killed with signal 11
24 Correct 9 ms 14420 KB Output is correct
25 Correct 13 ms 14488 KB Output is correct
26 Correct 39 ms 14676 KB Output is correct
27 Correct 218 ms 15728 KB Output is correct
28 Execution timed out 2039 ms 22356 KB Time limit exceeded
29 Correct 14 ms 14420 KB Output is correct
30 Correct 33 ms 14720 KB Output is correct
31 Correct 215 ms 15604 KB Output is correct
32 Execution timed out 2082 ms 25404 KB Time limit exceeded
33 Correct 8 ms 14416 KB Output is correct
34 Correct 8 ms 14344 KB Output is correct
35 Correct 18 ms 14548 KB Output is correct
36 Correct 23 ms 14584 KB Output is correct
37 Correct 190 ms 15472 KB Output is correct
38 Correct 294 ms 15960 KB Output is correct
39 Correct 8 ms 14360 KB Output is correct
40 Correct 12 ms 14420 KB Output is correct
41 Correct 22 ms 14668 KB Output is correct
42 Correct 21 ms 14576 KB Output is correct
43 Correct 46 ms 14676 KB Output is correct
44 Correct 82 ms 15032 KB Output is correct
45 Correct 175 ms 15656 KB Output is correct
46 Correct 291 ms 15784 KB Output is correct
47 Execution timed out 2061 ms 26860 KB Time limit exceeded