답안 #758010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758010	2023-06-14T04:42:45 Z	SanguineChameleon	Archery (IOI09_archery)	C++17	22 / 100	2000 ms	3628 KB

archery

#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 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]++;
		}
	}
	vector<int> free;
	int sz = 0;
	for (int i = 1; i <= N; i++) {
		if (cnt[i] == 2) {
			if (sz > 0) {
				cnt[--sz] = 1;
			}
			else {
				free.push_back(i);
			}
			cnt[i] = 1;
		}
		else {
			if (cnt[1] == 1) {
				free.push_back(i);
				cnt[1] = 0;
			}
			if (cnt[i] == 0 && i > 1) {
				holes[sz++] = i;
			}
		}
	}
	reverse(free.begin(), free.end());
	for (int i = N; i > 1 && !free.empty(); i--) {
		if (cnt[i] == 0) {
			free.pop_back();
			cnt[i] = 1;
		}
	}
	for (auto i: free) {
		cnt[((i - 1) + N - R % N) % N + 1]++;
	}
}

int solve(int start) {
	if (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 (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

4.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Incorrect	18 ms	340 KB	Output isn't correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct

Subtask #2

18.0 / 94.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	340 KB	Output isn't correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Incorrect	12 ms	372 KB	Output isn't correct
4	Incorrect	1585 ms	596 KB	Output isn't correct
5	Execution timed out	2054 ms	3080 KB	Time limit exceeded
6	Incorrect	1 ms	340 KB	Output isn't correct
7	Incorrect	2 ms	340 KB	Output isn't correct
8	Correct	217 ms	688 KB	Output is correct
9	Incorrect	384 ms	724 KB	Output isn't correct
10	Correct	1 ms	340 KB	Output is correct
11	Incorrect	1120 ms	760 KB	Output isn't correct
12	Incorrect	5 ms	340 KB	Output isn't correct
13	Incorrect	1343 ms	2680 KB	Output isn't correct
14	Incorrect	41 ms	428 KB	Output isn't correct
15	Incorrect	1321 ms	892 KB	Output isn't correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	2 ms	340 KB	Output is correct
18	Incorrect	3 ms	340 KB	Output isn't correct
19	Correct	6 ms	340 KB	Output is correct
20	Incorrect	11 ms	460 KB	Output isn't correct
21	Incorrect	217 ms	772 KB	Output isn't correct
22	Correct	237 ms	836 KB	Output is correct
23	Execution timed out	2098 ms	3628 KB	Time limit exceeded
24	Incorrect	1 ms	340 KB	Output isn't correct
25	Incorrect	3 ms	340 KB	Output isn't correct
26	Incorrect	52 ms	340 KB	Output isn't correct
27	Execution timed out	2070 ms	596 KB	Time limit exceeded
28	Execution timed out	2085 ms	2464 KB	Time limit exceeded
29	Correct	1 ms	340 KB	Output is correct
30	Correct	12 ms	340 KB	Output is correct
31	Incorrect	167 ms	700 KB	Output isn't correct
32	Execution timed out	2090 ms	3600 KB	Time limit exceeded
33	Incorrect	1 ms	340 KB	Output isn't correct
34	Correct	0 ms	212 KB	Output is correct
35	Incorrect	3 ms	340 KB	Output isn't correct
36	Incorrect	3 ms	340 KB	Output isn't correct
37	Incorrect	27 ms	612 KB	Output isn't correct
38	Incorrect	169 ms	724 KB	Output isn't correct
39	Incorrect	1 ms	340 KB	Output isn't correct
40	Incorrect	1 ms	340 KB	Output isn't correct
41	Incorrect	2 ms	340 KB	Output isn't correct
42	Incorrect	9 ms	340 KB	Output isn't correct
43	Incorrect	13 ms	428 KB	Output isn't correct
44	Incorrect	29 ms	508 KB	Output isn't correct
45	Incorrect	94 ms	660 KB	Output isn't correct
46	Incorrect	318 ms	696 KB	Output isn't correct
47	Execution timed out	2097 ms	3572 KB	Time limit exceeded