Submission #336983

#	Time	Username	Problem	Language	Result	Execution time	Memory
336983		gs14004	Archery (IOI09_archery)	C++17	74 / 100	2091 ms	11628 KiB

archery

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 400005;
const int mod = 1e9 + 7;
 
int n, r, a[MAXN], b[MAXN];
int cnt[MAXN][3];
 
int Do(int r, int s){
	if(s == 1) return 0;
	if(s <= n+1){
		memset(cnt, 0, sizeof(cnt));
		auto mode = [&](int x){
			if(x < s) return 0;
			if(x == s) return 1;
			return 2;
		};
		for(int i = 0; i < n; i++){
			cnt[i][mode(a[i])]++;
			cnt[i][mode(a[i + n])]++;
		}
		int winner = 0;
		int rotated = 0;
		while(!cnt[0][winner]) winner++;
		cnt[0][winner]--;
		int cand[3] = {};
		for(int i = 1; i <= 3 * n; i++){
			for(int j=0; j<3; j++){
				cand[j] += cnt[(i-1)%n][j];
				cnt[(i-1)%n][j] = 0;
			}
			int loser = 0;
			while(!cand[loser]) loser++;
			cand[loser]--;
			if(winner > loser) swap(winner, loser);
			// deport loser after round i
			cnt[(i-1)%n][loser]++;
			if(loser == 1){
				rotated++;
				if(i > 2 * n){
					int will_move = (r + n - i) % n;
					if(r < i) rotated--;
					return (n - 1 - will_move) % n - (rotated) * n;
				}
			}
		}
		assert(0);
	}
	int rot = 0;
	for(int i=0; i<r; i++){
		for(int j=0; j<n; j++){
			if(a[j] > a[j+n]) swap(a[j], a[j+n]);
		}
		swap(a[0], a[n]);
		if(a[0] == s) rot++;
		rotate(a, a + 1, a + n);
	}
	int pos = (find(a, a + 2 * n, s) - a) % n - rot * n;
	return pos;
}
 
mt19937 rng(0x14004);
 
int main(){
	scanf("%d %d",&n,&r);
	for(int i=0; i<2*n; i++){
		scanf("%d",&b[i]);
	}
	r = (r % n) + 2 * n;
	int s = 0, e = n - 1;
	auto fn = [&](int i){
		vector<int> foo(b, b + 2 * n);
		rotate(foo.begin(), foo.begin() + 1, foo.begin() + 2 * i + 1);
		for(int i=0; i<n; i++){
			a[i] = foo[2*i];
			a[i+n] = foo[2*i+1];
		}
		return Do(r, b[0]);
	};
	auto Mod = [&](int x){ return (x % n + n) % n; };
	int qq = fn(n - 1);
	while(s != e){
		int m = (s + e) / 2;
		if(fn(m) >= qq - Mod(qq)) e = m;
		else s = m + 1;
	}
	int rr = fn(s);
	s = 0, e = n - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		if(fn(m) <= rr) s = m;
		else e = m - 1;
	}
	cout << s + 1 << endl;
}

Compilation message (stderr)

archery.cpp: In function 'int main()':
archery.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d %d",&n,&r);
      |  ~~~~~^~~~~~~~~~~~~~~
archery.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%d",&b[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 68 / 94