oj.uz

Submission #744685

# Submission time Handle Problem Language Result Execution time Memory
744685 2023-05-19T01:06:04 Z oolimry Archery (IOI09_archery) C++17
0 / 100
 27 ms 29180 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 <= 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

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 29108 KB Execution killed with signal 11
2 Runtime error 24 ms 29128 KB Execution killed with signal 11
3 Runtime error 22 ms 29084 KB Execution killed with signal 11
4 Runtime error 24 ms 29056 KB Execution killed with signal 11
5 Runtime error 21 ms 29140 KB Execution killed with signal 11
6 Runtime error 25 ms 29140 KB Execution killed with signal 11

Subtask #2
0 / 94.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 29128 KB Execution killed with signal 11
2 Runtime error 21 ms 29140 KB Execution killed with signal 11
3 Runtime error 25 ms 29052 KB Execution killed with signal 11
4 Runtime error 21 ms 29108 KB Execution killed with signal 11
5 Runtime error 27 ms 29104 KB Execution killed with signal 11
6 Runtime error 21 ms 29140 KB Execution killed with signal 11
7 Runtime error 21 ms 29140 KB Execution killed with signal 11
8 Runtime error 22 ms 29140 KB Execution killed with signal 11
9 Runtime error 23 ms 29084 KB Execution killed with signal 11
10 Runtime error 22 ms 29144 KB Execution killed with signal 11
11 Runtime error 24 ms 29136 KB Execution killed with signal 11
12 Runtime error 21 ms 29140 KB Execution killed with signal 11
13 Runtime error 24 ms 29176 KB Execution killed with signal 11
14 Runtime error 21 ms 29096 KB Execution killed with signal 11
15 Runtime error 27 ms 29112 KB Execution killed with signal 11
16 Runtime error 20 ms 29140 KB Execution killed with signal 11
17 Runtime error 21 ms 29136 KB Execution killed with signal 11
18 Runtime error 21 ms 29140 KB Execution killed with signal 11
19 Runtime error 22 ms 29128 KB Execution killed with signal 11
20 Runtime error 22 ms 29140 KB Execution killed with signal 11
21 Runtime error 27 ms 29152 KB Execution killed with signal 11
22 Runtime error 26 ms 29172 KB Execution killed with signal 11
23 Runtime error 22 ms 29128 KB Execution killed with signal 11
24 Runtime error 20 ms 29140 KB Execution killed with signal 11
25 Runtime error 22 ms 29172 KB Execution killed with signal 11
26 Runtime error 21 ms 29064 KB Execution killed with signal 11
27 Runtime error 20 ms 29140 KB Execution killed with signal 11
28 Runtime error 24 ms 29096 KB Execution killed with signal 11
29 Runtime error 24 ms 29128 KB Execution killed with signal 11
30 Runtime error 21 ms 29072 KB Execution killed with signal 11
31 Runtime error 21 ms 29076 KB Execution killed with signal 11
32 Runtime error 23 ms 29128 KB Execution killed with signal 11
33 Runtime error 26 ms 29140 KB Execution killed with signal 11
34 Runtime error 23 ms 29124 KB Execution killed with signal 11
35 Runtime error 22 ms 29096 KB Execution killed with signal 11
36 Runtime error 22 ms 29068 KB Execution killed with signal 11
37 Runtime error 25 ms 29108 KB Execution killed with signal 11
38 Runtime error 22 ms 29152 KB Execution killed with signal 11
39 Runtime error 23 ms 29112 KB Execution killed with signal 11
40 Runtime error 21 ms 29140 KB Execution killed with signal 11
41 Runtime error 26 ms 29072 KB Execution killed with signal 11
42 Runtime error 25 ms 29180 KB Execution killed with signal 11
43 Runtime error 23 ms 29128 KB Execution killed with signal 11
44 Runtime error 22 ms 29140 KB Execution killed with signal 11
45 Runtime error 26 ms 29140 KB Execution killed with signal 11
46 Runtime error 22 ms 29140 KB Execution killed with signal 11
47 Runtime error 22 ms 29052 KB Execution killed with signal 11