답안 #349315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349315 2021-01-17T11:58:42 Z Mefarnis Archery (IOI09_archery) C++14
20 / 100
2000 ms 65540 KB
#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

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]);
      |   ~~~~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 2092 ms 35880 KB Time limit exceeded
3 Correct 19 ms 532 KB Output is correct
4 Runtime error 153 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Correct 1 ms 384 KB Output is correct
6 Correct 153 ms 1156 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 166 ms 1336 KB Output is correct
3 Execution timed out 2054 ms 31880 KB Time limit exceeded
4 Runtime error 88 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 133 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Correct 139 ms 1088 KB Output is correct
7 Execution timed out 2094 ms 13460 KB Time limit exceeded
8 Runtime error 92 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 89 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 2089 ms 20296 KB Time limit exceeded
11 Runtime error 91 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 140 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 117 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 99 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 92 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Correct 173 ms 1424 KB Output is correct
17 Execution timed out 2101 ms 27000 KB Time limit exceeded
18 Execution timed out 2047 ms 63768 KB Time limit exceeded
19 Runtime error 119 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 100 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 90 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 90 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 133 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Correct 167 ms 1392 KB Output is correct
25 Execution timed out 2099 ms 16144 KB Time limit exceeded
26 Runtime error 102 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 91 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 125 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Execution timed out 2089 ms 35668 KB Time limit exceeded
30 Runtime error 101 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 87 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 136 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Correct 163 ms 1168 KB Output is correct
34 Correct 164 ms 1192 KB Output is correct
35 Runtime error 180 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 154 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 93 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 93 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Correct 141 ms 1004 KB Output is correct
40 Execution timed out 2091 ms 16308 KB Time limit exceeded
41 Runtime error 180 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 157 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
43 Runtime error 101 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Runtime error 92 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
45 Runtime error 88 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
46 Runtime error 89 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
47 Runtime error 143 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)