oj.uz

답안 #744686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744686 2023-05-19T01:06:33 Z oolimry Archery (IOI09_archery) C++17
46 / 100
 2000 ms 48352 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
		assert(false);
		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 <= 2*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 <= 2*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(){
	//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 < 1;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:92:1: warning: control reaches end of non-void function [-Wreturn-type]
   92 | }
      | ^

Subtask #1
4.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14368 KB Output is correct
2 Correct 8 ms 14392 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 22 ms 14804 KB Output is correct
5 Runtime error 24 ms 29068 KB Execution killed with signal 6
6 Runtime error 20 ms 29060 KB Execution killed with signal 6

Subtask #2
42.0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14356 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 16 ms 14676 KB Output is correct
4 Correct 131 ms 17056 KB Output is correct
5 Execution timed out 2082 ms 33524 KB Time limit exceeded
6 Correct 8 ms 14420 KB Output is correct
7 Correct 11 ms 14420 KB Output is correct
8 Correct 102 ms 17148 KB Output is correct
9 Correct 197 ms 17856 KB Output is correct
10 Correct 12 ms 14548 KB Output is correct
11 Correct 212 ms 18540 KB Output is correct
12 Correct 27 ms 15032 KB Output is correct
13 Correct 1848 ms 48352 KB Output is correct
14 Correct 44 ms 15516 KB Output is correct
15 Correct 316 ms 22292 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 18 ms 14704 KB Output is correct
18 Correct 20 ms 14800 KB Output is correct
19 Correct 30 ms 14980 KB Output is correct
20 Correct 40 ms 15160 KB Output is correct
21 Correct 213 ms 18636 KB Output is correct
22 Correct 259 ms 17944 KB Output is correct
23 Execution timed out 2074 ms 42560 KB Time limit exceeded
24 Runtime error 22 ms 29076 KB Execution killed with signal 6
25 Runtime error 21 ms 29132 KB Execution killed with signal 6
26 Runtime error 21 ms 29140 KB Execution killed with signal 6
27 Runtime error 25 ms 29744 KB Execution killed with signal 6
28 Runtime error 41 ms 32996 KB Execution killed with signal 6
29 Runtime error 20 ms 29140 KB Execution killed with signal 6
30 Runtime error 22 ms 29156 KB Execution killed with signal 6
31 Runtime error 27 ms 29676 KB Execution killed with signal 6
32 Runtime error 50 ms 34600 KB Execution killed with signal 6
33 Runtime error 20 ms 28980 KB Execution killed with signal 6
34 Runtime error 23 ms 29012 KB Execution killed with signal 6
35 Runtime error 23 ms 29172 KB Execution killed with signal 6
36 Runtime error 21 ms 29140 KB Execution killed with signal 6
37 Runtime error 25 ms 29516 KB Execution killed with signal 6
38 Runtime error 25 ms 29804 KB Execution killed with signal 6
39 Runtime error 20 ms 29012 KB Execution killed with signal 6
40 Runtime error 20 ms 29004 KB Execution killed with signal 6
41 Runtime error 20 ms 29060 KB Execution killed with signal 6
42 Runtime error 21 ms 29160 KB Execution killed with signal 6
43 Runtime error 21 ms 29140 KB Execution killed with signal 6
44 Runtime error 22 ms 29368 KB Execution killed with signal 6
45 Runtime error 27 ms 29660 KB Execution killed with signal 6
46 Runtime error 27 ms 29688 KB Execution killed with signal 6
47 Runtime error 53 ms 35380 KB Execution killed with signal 6