Submission #476971

#	Time	Username	Problem	Language	Result	Execution time	Memory
476971		Drew_	Xylophone (JOI18_xylophone)	C++17	47 / 100	112 ms	356 KiB

xylophone

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

int a[5069];
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;
	if (l-1 >= 1)
	{
		int x = query(l-1, l);
		a[l-1] = 1 + x;
	}
	if (l+1 <= n)
	{
		int x = query(l, l+1);
		a[l+1] = 1 + x;
	}

	for (int i = l-2; i >= 1; --i)
	{
		int x = query(i, i+2), y = query(i, i+1), 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);
			}
		}
	}

	
	for (int i = l+2; i <= n; ++i)
	{
		int x = query(i-2, i), y = query(i-1, 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);
			}
		}
	}

	// 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: 0 / 53