Submission #284867

#	Time	Username	Problem	Language	Result	Execution time	Memory
284867		gs14004	Archery (IOI09_archery)	C++17	48 / 100	2091 ms	512 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 = 10005;
const int mod = 1e9 + 7;

int n, r, a[MAXN], b[MAXN];

int Do(int r, int s){
	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);
  assert(n <= 5000);
	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:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d %d",&n,&r);
      |  ~~~~~^~~~~~~~~~~~~~~
archery.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d",&b[i]);
      |   ~~~~~^~~~~~~~~~~~

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