제출 #476972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476972		Drew_	Xylophone (JOI18_xylophone)	C++17	100 / 100	76 ms	408 KiB

xylophone

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

constexpr int MAX = 5069;

int a[MAX];
bitset<MAX> used;
void solve(int n)
{
	int l = 1, r = n-1;
	while (l < r)
	{	
		int mid = (l + r + 1) >> 1;
		if (query(mid, n) == n-1) l = mid;
		else r = mid - 1;
	}

	a[l] = 1; used[a[l]] = true;
	if (l-1 >= 1)
	{
		int x = query(l-1, l);
		a[l-1] = 1 + x; used[a[l-1]] = true;
	}
	if (l+1 <= n)
	{
		int x = query(l, l+1);
		a[l+1] = 1 + x; used[a[l+1]] = true;
	}

	const auto valid = [&](int i) -> bool
	{
		return 1 <= i && i <= n;
	};

	for (int i = l-2; i >= 1; --i)
	{
		int y = query(i, i+1);
		bool p = false, q = false;

		if (valid(a[i+1] - y) && !used[a[i+1] - y])
			p = true;
		if (valid(a[i+1] + y) && !used[a[i+1] + y])
			q = true;

		if (p && q)
		{
			int x = query(i, i+2), z = abs(a[i+1] - a[i+2]);

			if (x == z)
			{
				if (a[i+2] > a[i+1]) a[i] = a[i+1] + y;
				else a[i] = a[i+1] - y;
			}
			else
			{
				if (a[i+2] > a[i+1])
				{
					if (x == y+z) a[i] = a[i+1] - y;
					else a[i] = a[i+2] + (x-z);
				}
				else
				{
					if (x == y+z) a[i] = a[i+1] + y;
					else a[i] = a[i+2] - (x-z);
				}
			}
		}
		else if (p) a[i] = a[i+1] - y;
		else a[i] = a[i+1] + y;

		used[a[i]] = true;
	}

	
	for (int i = l+2; i <= n; ++i)
	{
		int y = query(i-1, i);
		bool p = false, q = false;

		if (valid(a[i-1] - y) && !used[a[i-1] - y])
			p = true;
		if (valid(a[i-1] + y) && !used[a[i-1] + y])
			q = true;

		if (p && q)
		{
			int x = query(i-2, i), z = abs(a[i-2] - a[i-1]);
			if (x == z)
			{
				if (a[i-2] > a[i-1]) a[i] = a[i-1] + y;
				else a[i] = a[i-1] - y;
			}
			else
			{
				if (a[i-2] > a[i-1])
				{
					if (x == y+z) a[i] = a[i-1] - y;
					else a[i] = a[i-2] + (x-z);
				}
				else
				{ 
					if (x == y+z) a[i] = a[i-1] + y;
					else a[i] = a[i-2] - (x-z);
				}
			}
		}
		else if (p) a[i] = a[i-1] - y;
		else a[i] = a[i-1] + y;

		used[a[i]] = true;
	}

	// for (int i = 1; i <= n; ++i)
		// cerr << a[i] << " \n"[i == n];

	for (int i = 1; i <= n; ++i)
		answer(i, a[i]);
}

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