Submission #758313

#	Time	Username	Problem	Language	Result	Execution time	Memory
758313		SanguineChameleon	Archery (IOI09_archery)	C++17	46 / 100	254 ms	12536 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 {
	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 / 6
• Subtask 2: 40 / 94