Submission #758329

#	Time	Username	Problem	Language	Result	Execution time	Memory
758329		SanguineChameleon	Archery (IOI09_archery)	C++17	100 / 100	256 ms	12532 KiB

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 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 {
	int cnt[maxN][2];
	int sum[3];

	pair<int, int> simulate(int start) {
		for (int i = 0; i < maxN; i++) {
			for (int j = 0; j < 3; j++) {
				cnt[i][j] = 0;
			}
		}
		for (int i = 0; i < 3; i++) {
			sum[i] = 0;
		}
		for (int i = 1; i <= start * 2 - 1; i++) {
			int color = get_color(a[i]);
			int pos = (i + 1) / 2;
			if (color != BLACK) {
				cnt[pos][color]++;
			}
		}
		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 (color != BLACK) {
				cnt[pos][color]++;
			}
		}
		int pos = N;
		int wraps = 0;
		for (int iter = 0; iter < N * 3; iter++) {
			sum[WHITE] += cnt[pos][WHITE];
			sum[GRAY] += cnt[pos][GRAY];
			cnt[pos][WHITE] = 0;
			cnt[pos][GRAY] = 0;
			if (sum[WHITE] + sum[GRAY] >= 2) {
				if (pos == 1) {
					if (sum[GRAY] == 1) {
						cnt[pos][GRAY]++;
						sum[GRAY]--;
					}
					else {
						cnt[pos][WHITE]++;
						sum[WHITE]--;
					}
				}
				else {
					cnt[pos][WHITE]++;
					sum[WHITE]--;
				}
			}
			else if (sum[WHITE] + sum[GRAY] == 1) {
				if (pos == 1) {
					if (sum[GRAY] == 1) {
						wraps++;
					}
				}
				else {
					if (sum[WHITE] == 1) {
						cnt[pos][WHITE]++;
						sum[WHITE]--;
					}
					else {
						cnt[pos][GRAY]++;
						sum[GRAY]--;
					}
				}
			}
			if (pos == 1) {
				pos = N;
			}
			else {
				pos--;
			}
		}
		pos = -1;
		for (int i = 1; i <= N; i++) {
			if (cnt[i][GRAY] == 1) {
				pos = i;
				break;
			}
		}
		return make_pair(pos, wraps);
	}
}

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 (res1.first < res2.first) {
			return res1;
		}
		else {
			return res2;
		}
	}
	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;
}

Compilation message (stderr)

archery.cpp: In function 'std::pair<int, int> sub2::simulate(int)':
archery.cpp:135:15: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
  135 |     cnt[i][j] = 0;
      |     ~~~~~~~~~~^~~
archery.cpp:134:22: note: within this loop
  134 |    for (int j = 0; j < 3; j++) {
      |                    ~~^~~
archery.cpp:135:13: warning: array subscript 2 is above array bounds of 'int [2]' [-Warray-bounds]
  135 |     cnt[i][j] = 0;
      |     ~~~~~~~~^

• Subtask 1: 6 / 6
• Subtask 2: 94 / 94