Submission #349315

#	Time	Username	Problem	Language	Result	Execution time	Memory
349315		Mefarnis	Archery (IOI09_archery)	C++14	20 / 100	2101 ms	65540 KiB

archery

#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200000
#define pb push_back
using namespace std;
typedef pair<int,int> pi;

int n,k;
int ar[2*maxn];
int ansLast,ansInit;

void swaps(vector<pi>& vec) {
	for( int i = 0 ; i < n ; i++ )
		if(vec[i].fi > vec[i].se)
			swap(vec[i].fi,vec[i].se);
	/*
	for( int i = 0 ; i < n ; i++ )
		printf("%d %d , ",vec[i].fi,vec[i].se);
	puts("");
	*/
}

bool isSame(vector<pi>& a , vector<pi>& b) {
	for( int i = 0 ; i < n ; i++ )
		if(a[i] != b[i])
			return false;
	return true;
}

bool check(vector< vector<pi> >& vecs , vector<pi>& vec , int r) {
	for( int i = 0 ; i < r ; i++ )
		if(isSame(vecs[i],vec)) {
			int len = r-i;
			int rem = k-i;
			int add = rem % len;
			vec = vecs[i+add];
			return true;
		}
	return false;
}

void solve(int t) {
	// printf("t = %d\n",t);
	vector<pi> vec;
	vector< vector<pi> > vecs;
	for( int i = 0 ; i < n ; i++ )
		vec.pb(pi(0,0));
	vec[t].fi = ar[0];
	for( int i = 1 , idx = 0 ; i < 2*n ; i++ ) {
		if(vec[idx].fi == 0)
			vec[idx].fi = ar[i];
		else
			vec[idx++].se = ar[i];
	}
	swaps(vec);
	vecs.pb(vec);
	for( int r = 1 ; r <= k ; r++ ) {
		vector<pi> last = vec;
		for( int i = 1 ; i < n ; i++ ) {
			vec[i-1].fi = min(last[i].fi,last[i].se);
			vec[i].se = max(last[i].fi,last[i].se);
		}
		vec[0].se = min(last[0].fi,last[0].se);
		vec[n-1].fi = max(last[0].fi,last[0].se);
		swaps(vec);
		if(check(vecs,vec,r))
			break;
		vecs.pb(vec);
	}
	for( int i = 0 ; i < n ; i++ )
		if(vec[i].fi == ar[0] || vec[i].se == ar[0]) {
			if(i <= ansLast) {
				ansLast = i;
				ansInit = t;
			}
			break;
		}
}

int main() {
	scanf("%d%d",&n,&k);
	for( int i = 0 ; i < 2*n ; i++ )
		scanf("%d",&ar[i]);
	ansLast = n;
	for( int t = 0 ; t < n ; t++ )
		solve(t);
	printf("%d\n",ansInit+1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 4 / 6
• Subtask 2: 16 / 94