Submission #988951

# Submission time Handle Problem Language Result Execution time Memory
988951 2024-05-27T04:33:32 Z emptypringlescan Archery (IOI09_archery) C++17
31 / 100
2000 ms 604 KB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
int n;
long long r;
int arr[10005],brr[10005],at;
int calc(){
	if(arr[at]==1) return 1;
	for(int i=0; i<2*n; i++) brr[i]=arr[i];
	int ex[n];
	memset(ex,0,sizeof(ex));
	int rnd=min(n,400);
	for(int k=0; k<rnd; k++){
		for(int j=0; j<n; j++) ex[j]=0;
		if(brr[1]>brr[0]) ex[0]=1;
		for(int j=1; j<n; j++){
			if(brr[j<<1|1]<brr[j<<1]) ex[j]=1;
		}
		swap(brr[ex[0]],brr[(n-1)<<1|ex[n-1]]);
		for(int i=0; i<n-2; i++){
			swap(brr[i<<1|ex[i]],brr[(i+1)<<1|ex[i+1]]);
		}
	}
	int cur=0;
	for(int i=0; i<2*n; i++){
		if(arr[at]==brr[i]) cur=i/2;
	}
	if(arr[at]>n) return cur+1;
	cur-=r-rnd;
	cur%=n;
	if(cur<0) cur+=n;
	return cur+1;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> r;
	for(int i=0; i<2*n; i++){
		cin >> arr[i];
	}
	for(int i=0; i<2*n-1; i++) swap(arr[i],arr[i+1]);
	at=2*n-1;
	pair<int,int> ans={1e8,-1};
	for(int i=2*n-1; i>=max(0,2*n-4000); i-=2){
		int x=calc();
		//cout << i << ' ' << x << '\n';
		if(x<ans.first) ans={x,i};
		if(i){
			at--;
			swap(arr[i],arr[i-1]);
			at--;
			swap(arr[i-1],arr[i-2]);
		}
	}
	cout << ans.second/2+1;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 388 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Execution timed out 2098 ms 348 KB Time limit exceeded
5 Correct 0 ms 348 KB Output is correct
6 Correct 11 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 12 ms 464 KB Output is correct
3 Correct 1650 ms 468 KB Output is correct
4 Execution timed out 2037 ms 344 KB Time limit exceeded
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Correct 11 ms 460 KB Output is correct
7 Correct 509 ms 452 KB Output is correct
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Correct 1065 ms 592 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Execution timed out 2092 ms 348 KB Time limit exceeded
13 Runtime error 1 ms 600 KB Execution killed with signal 11
14 Execution timed out 2069 ms 348 KB Time limit exceeded
15 Runtime error 1 ms 604 KB Execution killed with signal 11
16 Correct 12 ms 348 KB Output is correct
17 Correct 1311 ms 464 KB Output is correct
18 Execution timed out 2063 ms 348 KB Time limit exceeded
19 Execution timed out 2029 ms 344 KB Time limit exceeded
20 Execution timed out 2021 ms 348 KB Time limit exceeded
21 Runtime error 1 ms 604 KB Execution killed with signal 11
22 Runtime error 1 ms 604 KB Execution killed with signal 11
23 Runtime error 1 ms 604 KB Execution killed with signal 11
24 Correct 12 ms 464 KB Output is correct
25 Correct 741 ms 460 KB Output is correct
26 Execution timed out 2047 ms 344 KB Time limit exceeded
27 Runtime error 2 ms 604 KB Execution killed with signal 11
28 Runtime error 1 ms 604 KB Execution killed with signal 11
29 Incorrect 1879 ms 468 KB Output isn't correct
30 Execution timed out 2054 ms 348 KB Time limit exceeded
31 Runtime error 1 ms 604 KB Execution killed with signal 11
32 Runtime error 1 ms 604 KB Execution killed with signal 11
33 Correct 12 ms 464 KB Output is correct
34 Correct 12 ms 464 KB Output is correct
35 Execution timed out 2047 ms 344 KB Time limit exceeded
36 Execution timed out 2068 ms 348 KB Time limit exceeded
37 Execution timed out 2035 ms 344 KB Time limit exceeded
38 Runtime error 1 ms 600 KB Execution killed with signal 11
39 Correct 13 ms 348 KB Output is correct
40 Incorrect 757 ms 460 KB Output isn't correct
41 Execution timed out 2076 ms 348 KB Time limit exceeded
42 Execution timed out 2055 ms 348 KB Time limit exceeded
43 Execution timed out 2041 ms 348 KB Time limit exceeded
44 Execution timed out 2044 ms 348 KB Time limit exceeded
45 Runtime error 1 ms 604 KB Execution killed with signal 11
46 Runtime error 1 ms 604 KB Execution killed with signal 11
47 Runtime error 1 ms 604 KB Execution killed with signal 11