Submission #759894

#	Time	Username	Problem	Language	Result	Execution time	Memory
759894		wenqi	Archery (IOI09_archery)	C++17	52 / 100	2092 ms	8488 KiB

archery

// trans rights
#include <bits/extc++.h>
using namespace std;
#define DIE assert(0);

int N, R;
int Q[400005], S;
int X[400005];

int cons[3];
int splash()
{
	for (int i = 0; i < 3; i++)
		if (cons[i])
			return i;
	DIE
}
int skilled()
{
	memset(cons, 0, sizeof(cons));
	int f = -1;
	deque<pair<int, int>> dq;
	for (int i = 0; i < 2 * N; i++)
		dq.push_back({X[i] + 1, i / 2 + 1});
	for (int r = 1; r <= 3 * N; r++)
	{
		while (r >= dq.front().second)
		{
			cons[dq.front().first]++;
			dq.pop_front();
		}
		int a = splash();
		cons[a]--;
		int b = splash();
		cons[b]--;
		if (a > b)
			swap(a, b);
		dq.push_back({b, N + r});
		cons[a]++;
		if (r >= 2 * N and b == 1)
			f = r;
	}
	assert(f != -1);
	int diff = (R - f + N) % N;
	return N - diff;
}

int cnt[200005][3];
int find_best(int p)
{
	for (int i = 0; i <= 2; i++)
		if (cnt[p][i])
			return i;
	DIE
}
int find_worst(int p)
{
	for (int i = 2; i >= 0; i--)
		if (cnt[p][i])
			return i;
	DIE
}
void zero(int p)
{
	for (int i = 0; i < 3; i++)
		cnt[p][i] = 0;
}
void mov(int i, int j, int (*f)(int))
{
	int h = f(i);
	cnt[i][h]--;
	for (int k = 0; k < 3; k++)
		cnt[j][k] += cnt[i][k];
	zero(i);
	cnt[i][h]++;
}
int washed()
{
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < 2 * N; i++)
		cnt[i / 2 + 1][X[i] + 1]++;
	for (int k = 0; k < 3; k++)
	{
		mov(1, N, find_best);
		for (int i = N; i > 1; i--)
			mov(i, i - 1, find_worst);
	}
	for (int i = 1; i <= N; i++)
	{
		if (cnt[i][1])
			return i;
	}
	DIE
}

void place(int p)
{
	for (int i = 0; i < 2 * p - 1; i++)
		X[i] = Q[i] > S ? 1 : -1;
	X[2 * p - 1] = 0;
	for (int i = 2 * p; i < 2 * N; i++)
		X[i] = Q[i - 1] > S ? 1 : -1;
}

int solve(int (*f)())
{
	pair<int, int> mn = {1e9, 0};
	for (int i = 1; i <= N; i++)
	{
		place(i);
		mn = min(mn, {f(), -i});
	}
	return -mn.second;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> R;
	R = (R - 2 * N) % N + 2 * N;
	cin >> S;
	for (int i = 0; i < 2 * N - 1; i++)
		cin >> Q[i];
	if (S == 1)
	{
		cout << N;
		return 0;
	}
	if (S < N + 2)
	{
		cout << solve(skilled);
		return 0;
	}
	cout << solve(washed);
	return 0;
}

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