Submission #740070

#	Time	Username	Problem	Language	Result	Execution time	Memory
740070		maeola	Xylophone (JOI18_xylophone)	C++17	100 / 100	107 ms	444 KiB

xylophone

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

static int g1[5005], g2[5005], A[5005];

void solve(int N)
{
	for (int i = 1; i <= N - 1; i++)
		g1[i] = query(i, i + 1);
	for (int i = 1; i <= N - 2; i++)
		g2[i] = query(i, i + 2);

	A[1] = 0;
	A[2] = g1[1];
	for (int i = 3; i <= N; i++)
	{
		// A[i - 1] + g1[i - 1]
		// A[i - 1] - g1[i - 1]
		if (g1[i - 2] + g1[i - 1] == g2[i - 2])
		{
			if (A[i - 1] > A[i - 2])
			{
				A[i] = A[i - 1] + g1[i - 1];
			}else{
				A[i] = A[i - 1] - g1[i - 1];
			}
		}
		else
		{
			if (A[i - 1] > A[i - 2])
			{
				A[i] = A[i - 1] - g1[i - 1];
			}else{
				A[i] = A[i - 1] + g1[i - 1];
			}
		}
	}
	auto mni = min_element(A + 1, A + 1 + N) - A;
	auto mxi = max_element(A + 1, A + 1 + N) - A;
	if (mni > mxi)
	{
		for (int i = 1; i <= N; i++)
			A[i] = -A[i];
	}
	auto mn = *min_element(A + 1, A + 1 + N);
	for (int i = 1; i <= N; i++)
		answer(i, A[i] - mn + 1);
}

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