Submission #364374

#	Time	Username	Problem	Language	Result	Execution time	Memory
364374		Rainbowbunny	Xylophone (JOI18_xylophone)	C++17	100 / 100	121 ms	624 KiB

xylophone

#include "xylophone.h"
#include <algorithm>

int a[5005], c[5005], d[5005];

void solve(int n)
{
	for(int i = 1; i < n; i++)
	{
		c[i] = query(i, i + 1);
	}
	for(int i = 1; i + 1 < n; i++)
	{
		d[i] = query(i, i + 2);
	}
	a[1] = 0;
	a[2] = c[1];
	for(int i = 3; i <= n; i++)
	{
		int upper = a[i - 1] + c[i - 1];
		int lower = a[i - 1] - c[i - 1];
		if(d[i - 2] == std::max({a[i - 2], a[i - 1], upper}) - std::min({a[i - 2], a[i - 1], upper}))
		{
			a[i] = upper;
		}
		else
		{
			a[i] = lower;
		}
	}
	int idmin = 1, idmax = 1;
	for(int i = 1; i <= n; i++)
	{
		if(a[idmin] > a[i])
		{
			idmin = i;
		}
		if(a[idmax] < a[i])
		{
			idmax = i;
		}
	}
	if(idmin > idmax)
	{
		for(int i = 1; i <= n; i++)
		{
			a[i] = -a[i];
		}
	}	
	int value = 1 - a[std::min(idmin, idmax)];
	for(int i = 1; i <= n; i++)
	{
		a[i] += value;
		answer(i, a[i]);
	}
}

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