oj.uz

답안 #744683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744683 2023-05-19T01:04:55 Z oolimry Archery (IOI09_archery) C++17
0 / 100
 26 ms 29252 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
		assert(false);
		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(){
	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 main()':
archery.cpp:124:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  freopen("i.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~
archery.cpp: In function 'int solve(int)':
archery.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
   92 | }
      | ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 29140 KB Execution killed with signal 6
2 Runtime error 21 ms 29140 KB Execution killed with signal 6
3 Runtime error 21 ms 29204 KB Execution killed with signal 6
4 Runtime error 21 ms 29140 KB Execution killed with signal 6
5 Runtime error 21 ms 29124 KB Execution killed with signal 6
6 Runtime error 22 ms 29224 KB Execution killed with signal 6

Subtask #2
0 / 94.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 29140 KB Execution killed with signal 6
2 Runtime error 21 ms 29140 KB Execution killed with signal 6
3 Runtime error 22 ms 29140 KB Execution killed with signal 6
4 Runtime error 25 ms 29140 KB Execution killed with signal 6
5 Runtime error 21 ms 29140 KB Execution killed with signal 6
6 Runtime error 25 ms 29140 KB Execution killed with signal 6
7 Runtime error 22 ms 29212 KB Execution killed with signal 6
8 Runtime error 22 ms 29184 KB Execution killed with signal 6
9 Runtime error 22 ms 29124 KB Execution killed with signal 6
10 Runtime error 23 ms 29124 KB Execution killed with signal 6
11 Runtime error 22 ms 29140 KB Execution killed with signal 6
12 Runtime error 22 ms 29128 KB Execution killed with signal 6
13 Runtime error 22 ms 29140 KB Execution killed with signal 6
14 Runtime error 22 ms 29140 KB Execution killed with signal 6
15 Runtime error 21 ms 29140 KB Execution killed with signal 6
16 Runtime error 22 ms 29132 KB Execution killed with signal 6
17 Runtime error 22 ms 29140 KB Execution killed with signal 6
18 Runtime error 21 ms 29132 KB Execution killed with signal 6
19 Runtime error 23 ms 29112 KB Execution killed with signal 6
20 Runtime error 23 ms 29116 KB Execution killed with signal 6
21 Runtime error 24 ms 29128 KB Execution killed with signal 6
22 Runtime error 21 ms 29116 KB Execution killed with signal 6
23 Runtime error 24 ms 29120 KB Execution killed with signal 6
24 Runtime error 21 ms 29176 KB Execution killed with signal 6
25 Runtime error 22 ms 29160 KB Execution killed with signal 6
26 Runtime error 25 ms 29252 KB Execution killed with signal 6
27 Runtime error 21 ms 29152 KB Execution killed with signal 6
28 Runtime error 22 ms 29108 KB Execution killed with signal 6
29 Runtime error 21 ms 29232 KB Execution killed with signal 6
30 Runtime error 23 ms 29152 KB Execution killed with signal 6
31 Runtime error 23 ms 29196 KB Execution killed with signal 6
32 Runtime error 22 ms 29116 KB Execution killed with signal 6
33 Runtime error 22 ms 29140 KB Execution killed with signal 6
34 Runtime error 21 ms 29208 KB Execution killed with signal 6
35 Runtime error 21 ms 29128 KB Execution killed with signal 6
36 Runtime error 22 ms 29204 KB Execution killed with signal 6
37 Runtime error 24 ms 29156 KB Execution killed with signal 6
38 Runtime error 23 ms 29164 KB Execution killed with signal 6
39 Runtime error 26 ms 29140 KB Execution killed with signal 6
40 Runtime error 22 ms 29140 KB Execution killed with signal 6
41 Runtime error 22 ms 29140 KB Execution killed with signal 6
42 Runtime error 22 ms 29208 KB Execution killed with signal 6
43 Runtime error 24 ms 29152 KB Execution killed with signal 6
44 Runtime error 22 ms 29140 KB Execution killed with signal 6
45 Runtime error 21 ms 29116 KB Execution killed with signal 6
46 Runtime error 22 ms 29200 KB Execution killed with signal 6
47 Runtime error 22 ms 29156 KB Execution killed with signal 6