Submission #1252588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252588		XXBabaProBerkay	Xylophone (JOI18_xylophone)	C++20	47 / 100	23 ms	456 KiB

xylophone

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

void solve(int N) {

	vector<int> ans(N + 1), dif(N + 1);
	for (int i = 1; i < N; i++)
		dif[i] = query(i, i + 1);

	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;
	}

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

		int x = dif[i - 2];
		int y = dif[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;
		}

		int z = query(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] || !ans[i + 2])
			continue;

		v[ans[i]] = 1;

		int x = dif[i + 1];
		int y = dif[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;
		}

		int z = query(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: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53