Submission #758020

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
758020	2023-06-14T04:52:44 Z	SanguineChameleon	Archery (IOI09_archery)	C++17	88 / 100	2000 ms	3548 KB

archery

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;
 
void just_do_it();
 
int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}
 
const int maxN = 2e5 + 20;
int a[maxN * 2];
int cnt1[maxN];
int cnt2[maxN];
int Free[maxN];
int holes[maxN];
int N, R, K;
 
void simulate(int start, int lim, int cnt[]) {
	for (int i = 1; i <= N; i++) {
		cnt[i] = 0;
	}
	for (int i = 1; i <= start * 2 - 1; i++) {
		if (a[i] >= lim) {
			cnt[(i + 1) / 2]++;
		}
	}
	if (K >= lim) {
		cnt[start]++;
	}
	for (int i = start * 2; i <= N * 2 - 1; i++) {
		if (a[i] >= lim) {
			cnt[i / 2 + 1]++;
		}
	}
	int free_sz = 0;
	int holes_sz = 0;
	for (int i = 1; i <= N; i++) {
		if (cnt[i] == 2) {
			if (holes_sz > 0) {
				cnt[holes[--holes_sz]] = 1;
			}
			else {
				Free[free_sz++] = i;
			}
			cnt[i] = 1;
		}
		else {
			if (cnt[1] == 1) {
				Free[free_sz++] = i;
				cnt[1] = 0;
			}
			if (cnt[i] == 0 && i > 1) {
				holes[holes_sz++] = i;
			}
		}
	}
	int free_pt = 0;
	for (int i = N; i > 1 && free_pt < free_sz; i--) {
		if (cnt[i] == 0) {
			free_pt++;
			cnt[i] = 1;
		}
	}
	for (; free_pt < free_sz; free_pt++) {
		int i = Free[free_pt];
		cnt[((i - 1) + N - R % N) % N + 1]++;
	}
}
 
int solve(int start) {
	if (N <= 5000 || start == 1) {
		simulate(start, K, cnt1);
	}
	else if (a[start * 2 - 2] < K) {
		if (a[start * 2 - 3] < K) {
			if (a[start * 2 - 1] < K) {
				if (cnt1[start] == 0) {
					cnt1[start - 1] = 0;
					cnt1[start] = 1;
				}
			}
		}
		else {
			if (a[start * 2 - 1] >= K) {
				if (cnt1[((start - 2) + N - R % N) % N + 1] == 2) {
					cnt1[((start - 2) + N - R % N) % N + 1] = 1;
					cnt1[((start - 1) + N - R % N) % N + 1] = 2;
				}
			}
			else {
				simulate(start, K, cnt1);
			}
		}
	}
	if (N <= 5000 || start == 1) {
		simulate(start, K + 1, cnt2);
	}
	else if (a[start * 2 - 2] > K) {
		if (a[start * 2 - 3] <= K) {
			if (start > 2 && a[start * 2 - 1] <= K) {
				if (cnt2[start - 1] == 0) {
					cnt2[start - 1] = 1;
					cnt2[start] = 0;
				}
			}
			else {
				simulate(start, K + 1, cnt2);
			}
		}
		else {
			if (a[start * 2 - 1] > K) {
				if (cnt2[((start - 1) + N - R % N) % N + 1] == 2) {
					cnt2[((start - 1) + N - R % N) % N + 1] = 1;
					cnt2[((start - 2) + N - R % N) % N + 1] = 2;
				}
			}
			else {
				simulate(start, K + 1, cnt2);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (cnt1[i] != cnt2[i]) {
			return i;
		}
	}
	return -1;
}
 
void just_do_it() {
	cin >> N >> R >> K;
	for (int i = 1; i <= N * 2 - 1; i++) {
		cin >> a[i];
	}
	if (N == 1) {
		cout << 1;
		return;
	}
	if (K == 1) {
		cout << N;
		return;
	}
	if (K == N * 2) {
		cout << 2;
		return;
	}
	pair<int, int> res = make_pair(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		res = min(res, make_pair(solve(i), -i));
	}
	cout << -res.second;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	155 ms	372 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct

Subtask #2

82.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	49 ms	340 KB	Output is correct
4	Correct	1435 ms	596 KB	Output is correct
5	Execution timed out	2074 ms	3024 KB	Time limit exceeded
6	Correct	1 ms	340 KB	Output is correct
7	Correct	17 ms	340 KB	Output is correct
8	Correct	183 ms	596 KB	Output is correct
9	Correct	372 ms	820 KB	Output is correct
10	Correct	43 ms	340 KB	Output is correct
11	Correct	1002 ms	696 KB	Output is correct
12	Correct	110 ms	340 KB	Output is correct
13	Execution timed out	2085 ms	2388 KB	Time limit exceeded
14	Correct	657 ms	420 KB	Output is correct
15	Correct	1429 ms	860 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	49 ms	340 KB	Output is correct
18	Correct	56 ms	368 KB	Output is correct
19	Correct	190 ms	340 KB	Output is correct
20	Correct	599 ms	428 KB	Output is correct
21	Correct	219 ms	724 KB	Output is correct
22	Correct	367 ms	724 KB	Output is correct
23	Execution timed out	2057 ms	3288 KB	Time limit exceeded
24	Correct	1 ms	340 KB	Output is correct
25	Correct	15 ms	340 KB	Output is correct
26	Correct	375 ms	432 KB	Output is correct
27	Correct	1874 ms	684 KB	Output is correct
28	Execution timed out	2073 ms	2380 KB	Time limit exceeded
29	Correct	17 ms	340 KB	Output is correct
30	Correct	193 ms	432 KB	Output is correct
31	Correct	181 ms	668 KB	Output is correct
32	Execution timed out	2050 ms	3284 KB	Time limit exceeded
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	42 ms	360 KB	Output is correct
36	Correct	57 ms	368 KB	Output is correct
37	Correct	59 ms	596 KB	Output is correct
38	Correct	299 ms	736 KB	Output is correct
39	Correct	2 ms	264 KB	Output is correct
40	Correct	11 ms	368 KB	Output is correct
41	Correct	41 ms	364 KB	Output is correct
42	Correct	57 ms	340 KB	Output is correct
43	Correct	251 ms	416 KB	Output is correct
44	Correct	48 ms	468 KB	Output is correct
45	Correct	135 ms	668 KB	Output is correct
46	Correct	325 ms	680 KB	Output is correct
47	Execution timed out	2059 ms	3548 KB	Time limit exceeded