Submission #363261

#	Time	Username	Problem	Language	Result	Execution time	Memory
363261		r57shell	Xylophone (JOI18_xylophone)	C++14	100 / 100	122 ms	624 KiB

xylophone

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

using namespace std;

static const int MAXN = 5000;
static int C[MAXN];

void solve(int N)
{
	if (N == 2)
	{
		answer(1, 1);
		answer(2, 2);
		return;
	}
	C[0] = 0;
	C[1] = query(1, 2);
	for (int i = 2; i < N; ++i)
	{
		int w = query(i, i+1);
		int w1 = query(i-1, i+1);
		int x = C[i-1] + w;
		int lmin = C[i-1];
		int lmax = C[i-2];
		if (lmin > lmax)
			swap(lmin, lmax);
		//printf("%d(%d?)",w,x);
		if (max(x, lmax) - min(x, lmin) == w1)
		{
		}
		else
		{
			x = C[i-1] - w;
			//printf("(%d?)",x);
			//if (max(x, lmax) - min(x, lmin) == w1)
			//{
			//}
			//else
				//printf("wut");
		}
		//printf("\n");
		C[i] = x;
	}
	pair<int,int> m1(int(1e9),0);
	pair<int,int> m2(int(-1e9),0);
	for (int i = 0; i < N; ++i)
	{
		m1 = min(m1, pair<int,int>(C[i], i));
		m2 = max(m2, pair<int,int>(C[i], i));
	}
	if (m1.second < m2.second)
	{
		//for (int i = 0; i < N; ++i)
		//	printf("%d ", C[i]-m1.first+1);
		for (int i = 0; i < N; ++i)
			answer(i+1, C[i]-m1.first+1);
	}
	else
	{
		//for (int i = 0; i < N; ++i)
		//	printf("%d ", m2.first-C[i]+1);
		for (int i = 0; i < N; ++i)
			answer(i+1, m2.first-C[i]+1);
	}
}

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