Submission #758021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
758021	2023-06-14T04:55:50 Z	SanguineChameleon	Archery (IOI09_archery)	C++17	88 / 100	2000 ms	3532 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];
		int j = ((i - 1) + N - R) + 1;
		if (j > N) {
			j -= N;
		}
		cnt[j]++;
	}
}
 
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) {
				int j = ((start - 2) + N - R) + 1;
				if (j > N) {
					j -= N;
				}
				int k = ((start - 1) + N - R) + 1;
				if (k > N) {
					k -= N;
				}
				if (cnt1[j] == 2) {
					cnt1[j] = 1;
					cnt1[k] = 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) {
				int j = ((start - 1) + N - R) + 1;
				if (j > N) {
					j -= N;
				}
				int k = ((start - 2) + N - R) + 1;
				if (k > N) {
					k -= N;
				}
				if (cnt2[j] == 2) {
					cnt2[j] = 1;
					cnt2[k] = 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;
	R %= N;
	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	1 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	121 ms	376 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct

Subtask #2

82.0 / 94.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	36 ms	340 KB	Output is correct
4	Correct	1343 ms	596 KB	Output is correct
5	Execution timed out	2065 ms	3108 KB	Time limit exceeded
6	Correct	2 ms	340 KB	Output is correct
7	Correct	14 ms	364 KB	Output is correct
8	Correct	118 ms	628 KB	Output is correct
9	Correct	314 ms	692 KB	Output is correct
10	Correct	26 ms	340 KB	Output is correct
11	Correct	862 ms	704 KB	Output is correct
12	Correct	119 ms	376 KB	Output is correct
13	Execution timed out	2074 ms	2412 KB	Time limit exceeded
14	Correct	467 ms	420 KB	Output is correct
15	Correct	1411 ms	860 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	30 ms	340 KB	Output is correct
18	Correct	65 ms	356 KB	Output is correct
19	Correct	184 ms	388 KB	Output is correct
20	Correct	400 ms	340 KB	Output is correct
21	Correct	164 ms	724 KB	Output is correct
22	Correct	373 ms	816 KB	Output is correct
23	Execution timed out	2068 ms	3324 KB	Time limit exceeded
24	Correct	1 ms	340 KB	Output is correct
25	Correct	16 ms	340 KB	Output is correct
26	Correct	381 ms	420 KB	Output is correct
27	Correct	1836 ms	688 KB	Output is correct
28	Execution timed out	2066 ms	2388 KB	Time limit exceeded
29	Correct	17 ms	340 KB	Output is correct
30	Correct	192 ms	428 KB	Output is correct
31	Correct	173 ms	672 KB	Output is correct
32	Execution timed out	2072 ms	3276 KB	Time limit exceeded
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	43 ms	376 KB	Output is correct
36	Correct	59 ms	340 KB	Output is correct
37	Correct	57 ms	596 KB	Output is correct
38	Correct	264 ms	724 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	10 ms	468 KB	Output is correct
41	Correct	43 ms	340 KB	Output is correct
42	Correct	58 ms	340 KB	Output is correct
43	Correct	248 ms	416 KB	Output is correct
44	Correct	43 ms	468 KB	Output is correct
45	Correct	137 ms	664 KB	Output is correct
46	Correct	297 ms	680 KB	Output is correct
47	Execution timed out	2077 ms	3532 KB	Time limit exceeded