oj.uz

Submission #744672

# Submission time Handle Problem Language Result Execution time Memory
744672 2023-05-18T23:38:48 Z oolimry Archery (IOI09_archery) C++17
42 / 100
 2000 ms 31664 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;

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){
	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); 
	
	//show3(valmod, bestVal, pos);	
	
	if(valmod <= bestVal){
		bestVal = valmod;
		bestPos = pos;
	}
}

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14352 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 1572 ms 15048 KB Output is correct
5 Correct 8 ms 14360 KB Output is correct
6 Correct 14 ms 14436 KB Output is correct

Subtask #2
36.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 15 ms 14420 KB Output is correct
3 Correct 524 ms 14556 KB Output is correct
4 Execution timed out 2063 ms 15896 KB Time limit exceeded
5 Execution timed out 2050 ms 30808 KB Time limit exceeded
6 Correct 15 ms 14420 KB Output is correct
7 Incorrect 191 ms 14636 KB Output isn't correct
8 Execution timed out 2078 ms 15916 KB Time limit exceeded
9 Execution timed out 2054 ms 16764 KB Time limit exceeded
10 Incorrect 335 ms 14552 KB Output isn't correct
11 Execution timed out 2070 ms 16868 KB Time limit exceeded
12 Execution timed out 2077 ms 14748 KB Time limit exceeded
13 Execution timed out 2054 ms 26648 KB Time limit exceeded
14 Execution timed out 2053 ms 15084 KB Time limit exceeded
15 Execution timed out 2058 ms 17792 KB Time limit exceeded
16 Correct 16 ms 14420 KB Output is correct
17 Correct 449 ms 14580 KB Output is correct
18 Correct 1077 ms 14652 KB Output is correct
19 Execution timed out 2066 ms 14812 KB Time limit exceeded
20 Execution timed out 2062 ms 14940 KB Time limit exceeded
21 Execution timed out 2068 ms 16844 KB Time limit exceeded
22 Execution timed out 2065 ms 17592 KB Time limit exceeded
23 Execution timed out 2041 ms 31664 KB Time limit exceeded
24 Correct 16 ms 14420 KB Output is correct
25 Correct 280 ms 14484 KB Output is correct
26 Execution timed out 2091 ms 14676 KB Time limit exceeded
27 Execution timed out 2078 ms 15964 KB Time limit exceeded
28 Execution timed out 2062 ms 23576 KB Time limit exceeded
29 Correct 538 ms 14420 KB Output is correct
30 Execution timed out 2027 ms 14676 KB Time limit exceeded
31 Execution timed out 2041 ms 15828 KB Time limit exceeded
32 Execution timed out 2053 ms 26572 KB Time limit exceeded
33 Correct 17 ms 14420 KB Output is correct
34 Correct 18 ms 14316 KB Output is correct
35 Correct 1192 ms 14564 KB Output is correct
36 Correct 1813 ms 14648 KB Output is correct
37 Execution timed out 2066 ms 15664 KB Time limit exceeded
38 Execution timed out 2085 ms 16212 KB Time limit exceeded
39 Correct 16 ms 14420 KB Output is correct
40 Correct 273 ms 14480 KB Output is correct
41 Correct 1275 ms 14564 KB Output is correct
42 Correct 1640 ms 14584 KB Output is correct
43 Execution timed out 2066 ms 14676 KB Time limit exceeded
44 Execution timed out 2063 ms 15108 KB Time limit exceeded
45 Execution timed out 2065 ms 15828 KB Time limit exceeded
46 Execution timed out 2023 ms 15956 KB Time limit exceeded
47 Execution timed out 2051 ms 28160 KB Time limit exceeded