Submission #958310

#	Time	Username	Problem	Language	Result	Execution time	Memory
958310		JwFXoiz	Xylophone (JOI18_xylophone)	C++14	47 / 100	125 ms	175604 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

int a[5001], qq[5001][5001];
int C = 0;

int ask(int l, int r)
{
	assert(++C <= 10000);
	if (qq[l][r] != -1) return qq[l][r];
	return qq[l][r] = query(l, r);
}

void calc(int l, int r, int f, int up)
{
	if (r - l <= 1) return;
	if (!f)
	{
		int x = ask(l + 1, r);
		int lx = l + 1, rx = r - 1;
		while (lx < rx)
		{
			int mid = (lx + rx + 1) >> 1;
			int y = ask(mid, r);
			if (x == y) lx = mid;
			else rx = mid - 1;
		}
		if (up) a[lx] = a[r] + x;
		else a[lx] = a[r] - x;
		calc(l, lx, 0, up ^ 1), calc(lx, r, 0, up);
	}
	else
	{
		int x = ask(l, r - 1);
		int lx = l + 1, rx = r - 1;
		while (lx < rx)
		{
			int mid = (lx + rx) >> 1;
			int y = ask(l, mid);
			if (x == y) rx = mid;
			else lx = mid + 1;
		}
		if (up) a[lx] = a[l] + x;
		else a[lx] = a[l] - x;
		calc(l, lx, 1, up), calc(lx, r, 1, up ^ 1);
	}
}

void solve(int N)
{
	for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) qq[i][j] = -1;
	int l = 1, r = N;
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if (ask(mid, N) == N - 1) l = mid;
		else r = mid - 1;
	}
	a[l] = 1;
	calc(0, l, 0, 1), calc(l, N + 1, 1, 1);
	for (int i = 1; i <= N; i++) 
	{
		answer(i, a[i]);
	}
}

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