Submission #958322

#	Time	Username	Problem	Language	Result	Execution time	Memory
958322		JwFXoiz	Xylophone (JOI18_xylophone)	C++14	100 / 100	73 ms	596 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
 
using namespace std;
 
void solve(int n)
{
	vector<int> d(n + 1), c(n + 1, 0);
	for (int i = 2; i <= n; i++) d[i] = query(i - 1, i);
	for (int i = 3; i <= n; i++)
	{
		c[i] = c[i - 1];
		if (query(i - 2, i) < d[i - 1] + d[i]) c[i] ^= 1;
	}
	for (int i = 2; i <= n; i++) 
	{
		if (c[i]) d[i] = -d[i];
	}
	array<int, 2> b = {-1, -1};
	for (int i = 1; i <= n; i++)
	{
		int s = 0;
		for (int j = i + 1; j <= n; j++)
		{
			s += d[j];
			if (abs(s) == n - 1)
			{
				b = {i, s};
				break;
			}
		}
	}
	if (b[1] < 0)
	{
		for (int i = 2; i <= n; i++) d[i] = -d[i];
	}
	int a[n + 1];
	a[b[0]] = 1;
	for (int i = b[0] + 1; i <= n; i++) a[i] = a[i - 1] + d[i];
	for (int i = b[0] - 1; i >= 1; i--) a[i] = a[i + 1] - d[i + 1];
	for (int i = 1; i <= n; i++) 
	{
		answer(i, a[i]);
	}
}

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