oj.uz

답안 #744678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744678 2023-05-19T00:48:09 Z oolimry Archery (IOI09_archery) C++17
84 / 100
 2000 ms 37592 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(){
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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