oj.uz

답안 #744681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744681 2023-05-19T01:01:45 Z oolimry Archery (IOI09_archery) C++17
88 / 100
 2000 ms 32992 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;
	}
	
	//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

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

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