Submission #1252616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252616		XXBabaProBerkay	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	408 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

void solve(int N) {
	vector<int> ans(N + 1), dif(N + 1), dif2(N);
	int l = 1, r = N - 1;
	while (l <= r)
	{
		int m = (l + r) / 2;

		if (query(m, N) == N - 1)
			l = m + 1;
		else r = m - 1;
	}

	auto f = [&](int l, int r)
	{
		if (r == l + 1 && dif[l])
			return dif[l];
		else if (r == l + 1)
			return dif[l] = query(l, r);

		if (r == l + 2 && dif2[l])
			return dif2[l];
		else if (r == l + 2)
			return dif2[l] = query(l, r);

		return query(l, r);
	};

	int one = r;
	ans[one] = 1;
	ans[one + 1] = 1 + f(one, one + 1);
	ans[one - 1] = 1 + f(one - 1, one);
	vector<bool> v(N + 1);
	v[1] = v[1 + f(one, one + 1)] = v[1 + f(one - 1, one)] = true;
	for (int i = 3; i <= N; i++)
	{
		if (ans[i]) continue;
		if (!ans[i - 1]) continue;
		v[ans[i]] = 1;

		int y = f(i - 1, i);

		if (ans[i - 1] - y < 1 || v[ans[i - 1] - y])
		{
			ans[i] = ans[i - 1] + y;
			continue;
		}
		if (ans[i - 1] + y > N || v[ans[i - 1] + y])
		{
			ans[i] = ans[i - 1] - y;
			continue;
		}

		if (!ans[i - 2]) continue;
		int x = f(i - 2, i - 1);
		int z = f(i - 2, i);
		if (ans[i - 2] < ans[i - 1])
		{
			if (z != x + y) ans[i] = ans[i - 1] - y;
			else ans[i] = ans[i - 1] + y;
		}
		else
		{
			if (z != x + y) ans[i] = ans[i - 1] + y;
			else ans[i] = ans[i - 1] - y;
		}
	}

	for (int i = N - 2; i >= 1; i--)
	{
		if (ans[i]) continue;
		if (!ans[i + 1]) continue;
		v[ans[i]] = 1;

		int x = f(i + 1, i + 2);
		int y = f(i, i + 1);

		if (ans[i + 1] - y < 1 || v[ans[i + 1] - y])
		{
			ans[i] = ans[i + 1] + y;
			continue;
		}
		if (ans[i + 1] + y > N || v[ans[i + 1] + y])
		{
			ans[i] = ans[i + 1] - y;
			continue;
		}

		if (!ans[i + 2]) continue;
		int z = f(i, i + 2);
		if (ans[i + 2] < ans[i + 1])
		{
			if (z != x + y) ans[i] = ans[i + 1] - y;
			else ans[i] = ans[i + 1] + y;
		}
		else
		{
			if (z != x + y) ans[i] = ans[i + 1] + y;
			else ans[i] = ans[i + 1] - y;
		}
	}

	for (int i = 1; i <= N; i++)
		answer(i, ans[i]);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53