oj.uz

Submission #744679

# Submission time Handle Problem Language Result Execution time Memory
744679 2023-05-19T00:55:28 Z oolimry Archery (IOI09_archery) C++17
41 / 100
 2000 ms 27772 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;
#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(){
	//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];	
	
	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 < 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
5.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 72 ms 14544 KB Output is correct
4 Execution timed out 2056 ms 20912 KB Time limit exceeded
5 Correct 14 ms 14340 KB Output is correct
6 Correct 149 ms 14796 KB Output is correct

Subtask #2
36.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14456 KB Output is correct
2 Correct 143 ms 14868 KB Output is correct
3 Correct 1303 ms 18504 KB Output is correct
4 Execution timed out 2074 ms 23168 KB Time limit exceeded
5 Execution timed out 2058 ms 26672 KB Time limit exceeded
6 Correct 144 ms 14792 KB Output is correct
7 Correct 406 ms 15540 KB Output is correct
8 Execution timed out 2066 ms 23156 KB Time limit exceeded
9 Execution timed out 2078 ms 23908 KB Time limit exceeded
10 Correct 521 ms 16048 KB Output is correct
11 Execution timed out 2069 ms 23800 KB Time limit exceeded
12 Execution timed out 2078 ms 21232 KB Time limit exceeded
13 Execution timed out 2057 ms 25348 KB Time limit exceeded
14 Execution timed out 2072 ms 21460 KB Time limit exceeded
15 Execution timed out 2054 ms 24460 KB Time limit exceeded
16 Correct 146 ms 14704 KB Output is correct
17 Correct 1142 ms 17928 KB Output is correct
18 Correct 1857 ms 20164 KB Output is correct
19 Execution timed out 2065 ms 21072 KB Time limit exceeded
20 Execution timed out 2067 ms 21560 KB Time limit exceeded
21 Execution timed out 2037 ms 24120 KB Time limit exceeded
22 Execution timed out 2066 ms 24248 KB Time limit exceeded
23 Execution timed out 2069 ms 27032 KB Time limit exceeded
24 Correct 139 ms 14672 KB Output is correct
25 Correct 880 ms 16920 KB Output is correct
26 Execution timed out 2061 ms 21128 KB Time limit exceeded
27 Execution timed out 2063 ms 22620 KB Time limit exceeded
28 Execution timed out 2063 ms 25384 KB Time limit exceeded
29 Correct 1349 ms 18368 KB Output is correct
30 Execution timed out 2063 ms 20888 KB Time limit exceeded
31 Execution timed out 2083 ms 22796 KB Time limit exceeded
32 Execution timed out 2074 ms 27080 KB Time limit exceeded
33 Correct 165 ms 14852 KB Output is correct
34 Correct 143 ms 14684 KB Output is correct
35 Correct 1963 ms 20444 KB Output is correct
36 Execution timed out 2069 ms 20824 KB Time limit exceeded
37 Execution timed out 2083 ms 22188 KB Time limit exceeded
38 Execution timed out 2079 ms 23004 KB Time limit exceeded
39 Correct 140 ms 14668 KB Output is correct
40 Correct 857 ms 16936 KB Output is correct
41 Correct 1950 ms 20528 KB Output is correct
42 Execution timed out 2076 ms 20652 KB Time limit exceeded
43 Execution timed out 2077 ms 21184 KB Time limit exceeded
44 Execution timed out 2068 ms 21488 KB Time limit exceeded
45 Execution timed out 2084 ms 22588 KB Time limit exceeded
46 Execution timed out 2077 ms 22736 KB Time limit exceeded
47 Execution timed out 2081 ms 27772 KB Time limit exceeded