oj.uz

Submission #758313

# Submission time Handle Problem Language Result Execution time Memory
758313 2023-06-14T12:27:05 Z SanguineChameleon Archery (IOI09_archery) C++17
46 / 100
 254 ms 12536 KB 
#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 WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

const int maxN = 2e5 + 20;
int a[maxN * 2];
pair<int, int> memo[maxN];
int N, R, K;

int get_color(int X) {
	if (X > K) {
		return WHITE;
	}
	else if (X < K) {
		return BLACK;
	}
	else {
		return GRAY;
	}
}

namespace sub1 {
	int cnt[maxN * 4][3];
	int sum[3];

	pair<int, int> simulate(int start) {
		for (int i = 0; i < maxN * 4; i++) {
			for (int j = 0; j < 3; j++) {
				cnt[i][j] = 0;
			}
		}
		for (int i = 0; i < 3; i++) {
			sum[i] = 0;
		}
		int color1 = -1;
		int color2 = -1;
		for (int i = 1; i <= start * 2 - 1; i++) {
			int color = get_color(a[i]);
			int pos = (i + 1) / 2;
			if (pos == 1) {
				if (color1 == -1) {
					color1 = color;
				}
				else {
					color2 = color;
				}
			}
			else {
				cnt[pos][color]++;
			}
		}
		if (start == 1) {
			if (color1 == -1) {
				color1 = GRAY;
			}
			else {
				color2 = GRAY;
			}
		}
		else {
			cnt[start][GRAY]++;
		}
		for (int i = start * 2; i <= N * 2 - 1; i++) {
			int color = get_color(a[i]);
			int pos = i / 2 + 1;
			if (pos == 1) {
				if (color1 == -1) {
					color1 = color;
				}
				else {
					color2 = color;
				}
			}
			else {
				cnt[pos][color]++;
			}
		}
		int first_gray = -1;
		int wraps = 0;
		for (int round = 1; round <= N * 3; round++) {
			if (round > N * 2 && (color1 == GRAY || color2 == GRAY)) {
				first_gray = round - 1;
				break;
			}
			if (color1 < color2) {
				swap(color1, color2);
			}
			if (color2 == GRAY) {
				wraps++;
			}
			cnt[round + N][color2]++;
			for (int i = 0; i < 3; i++) {
				sum[i] += cnt[round + 1][i];
			}
			for (int i = 2; i >= 0; i--) {
				if (sum[i] > 0) {
					color2 = i;
					sum[i]--;
					break;
				}
			}
		}
		if (R > first_gray) {
			wraps++;
		}
		int pos = (first_gray + N - R) % N + 1;
		return make_pair(pos, wraps);
	}
}


namespace sub2 {
	pair<int, int> simulate(int start) {
		assert(false);
		return make_pair(-1, -1);
	}
}

pair<int, int> get_final(int start) {
	if (memo[start].first != -1) {
		return memo[start];
	}
	if (K <= N + 1) {
		return (memo[start] = sub1::simulate(start));
	}
	else {
		return (memo[start] = sub2::simulate(start));
	}
}

pair<int, int> solve(int lt, int rt) {
	pair<int, int> final_lt = get_final(lt);
	pair<int, int> final_rt = get_final(rt);
	if (final_lt.second > final_rt.second) {
		int tmp_lt = lt;
		int tmp_rt = rt;
		int cut = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			pair<int, int> final_mt = get_final(mt);
			if (final_mt.second == final_lt.second) {
				cut = mt;
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		lt = tmp_lt;
		rt = tmp_rt;
		pair<int, int> res1 = solve(lt, cut);
		pair<int, int> res2 = solve(cut + 1, rt);
		if (res2.first < res1.first) {
			return res2;
		}
		else {
			return res1;
		}
	}
	else {
		pair<int, int> res = make_pair(-1, -1);
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			pair<int, int> final_mt = get_final(mt);
			if (final_mt.first == final_lt.first) {
				res = make_pair(final_mt.first, mt);
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		return res;
	}
}

void just_do_it() {
	cin >> N >> R >> K;
	R = N * 2 + 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;
	}
	for (int i = 1; i <= N; i++) {
		memo[i] = make_pair(-1, -1);
	}
	auto res = solve(1, N);
	cout << res.second;
}

Subtask #1
6.0 / 6.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 22 ms 9728 KB Output is correct
4 Correct 44 ms 9748 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
40.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9732 KB Output is correct
2 Correct 28 ms 9736 KB Output is correct
3 Correct 37 ms 9760 KB Output is correct
4 Correct 65 ms 9940 KB Output is correct
5 Correct 254 ms 12268 KB Output is correct
6 Incorrect 25 ms 9684 KB Output isn't correct
7 Correct 16 ms 9752 KB Output is correct
8 Correct 27 ms 9948 KB Output is correct
9 Correct 66 ms 10040 KB Output is correct
10 Correct 18 ms 9700 KB Output is correct
11 Correct 65 ms 9976 KB Output is correct
12 Correct 39 ms 9684 KB Output is correct
13 Correct 147 ms 11604 KB Output is correct
14 Correct 43 ms 9684 KB Output is correct
15 Correct 75 ms 10216 KB Output is correct
16 Correct 26 ms 9684 KB Output is correct
17 Correct 36 ms 9684 KB Output is correct
18 Correct 38 ms 9764 KB Output is correct
19 Incorrect 44 ms 9684 KB Output isn't correct
20 Correct 43 ms 9812 KB Output is correct
21 Correct 62 ms 9948 KB Output is correct
22 Incorrect 71 ms 10196 KB Output isn't correct
23 Correct 190 ms 12536 KB Output is correct
24 Runtime error 1 ms 468 KB Execution killed with signal 6
25 Runtime error 1 ms 468 KB Execution killed with signal 6
26 Runtime error 2 ms 596 KB Execution killed with signal 6
27 Runtime error 4 ms 1144 KB Execution killed with signal 6
28 Runtime error 22 ms 4528 KB Execution killed with signal 6
29 Runtime error 1 ms 596 KB Execution killed with signal 6
30 Runtime error 2 ms 596 KB Execution killed with signal 6
31 Runtime error 4 ms 1108 KB Execution killed with signal 6
32 Runtime error 30 ms 5964 KB Execution killed with signal 6
33 Runtime error 1 ms 468 KB Execution killed with signal 6
34 Runtime error 1 ms 468 KB Execution killed with signal 6
35 Runtime error 1 ms 596 KB Execution killed with signal 6
36 Runtime error 2 ms 596 KB Execution killed with signal 6
37 Runtime error 4 ms 980 KB Execution killed with signal 6
38 Runtime error 5 ms 1236 KB Execution killed with signal 6
39 Runtime error 1 ms 468 KB Execution killed with signal 6
40 Runtime error 1 ms 468 KB Execution killed with signal 6
41 Runtime error 2 ms 596 KB Execution killed with signal 6
42 Runtime error 2 ms 596 KB Execution killed with signal 6
43 Runtime error 2 ms 596 KB Execution killed with signal 6
44 Runtime error 2 ms 852 KB Execution killed with signal 6
45 Runtime error 4 ms 1108 KB Execution killed with signal 6
46 Runtime error 5 ms 1200 KB Execution killed with signal 6
47 Runtime error 33 ms 6868 KB Execution killed with signal 6