Submission #59711

#	Time	Username	Problem	Language	Result	Execution time	Memory
59711		MatheusLealV	Xylophone (JOI18_xylophone)	C++17	100 / 100	224 ms	20980 KiB

xylophone

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

int ans[5005][2], L[5005], R[5005];

int save[5005][5005];

int n,pos1, qtd[5005][2];

int Q(int a, int b)
{
	if(a >= b) return 0;

	if(save[a][b] != 0) return save[a][b];

	return save[a][b] = query(a, b);
}

int usado[5005];

void solve(int N)
{
	n = N;

	int subindo = 1, subindo2 = -1;

	ans[2][1] = -Q(1, 2);

	ans[2][0] = Q(1, 2);

	for(int p = 3; p <= n; p++)
	{
		int A = Q(p - 2, p), B = Q(p - 2, p - 1), C = Q(p - 1, p);

		if(A == B + C)
		{
			ans[p][0] = ans[p - 1][0] + C*subindo;

			ans[p][1] = ans[p - 1][1] + C*subindo2;
		}

		else
		{
			subindo *= -1;

			subindo2 *= -1;

			ans[p][0] = ans[p - 1][0] + C*subindo;

			ans[p][1] = ans[p - 1][1] + C*subindo2;
		}
	}


	for(int i = 1; i <= n; i++)
	{

		int P1 = -1, ok = 1;

		memset(usado, 0, sizeof usado);

		for(int j = 1; j <= n; j++)
		{
			if(i + ans[j][0] > n or i + ans[j][0] <= 0)
			{
				ok = 0;

				break;
			}

			if(i + ans[j][0] == 1) P1 = 1;

			if(i + ans[j][0] == n and P1 == -1) ok = 0;

			usado[i + ans[j][0]] = 1;
		}

		for(int j = 1; j <= n; j++)
			if(!usado[j]) ok = 0;

		if(ok)
		{
			for(int j = 1; j <= n; j++)
				answer(j, ans[j][0] + i);
			break;
		}

		memset(usado, 0, sizeof usado);

		ok = 1;

		P1 = -1;

		for(int j = 1; j <= n; j++)
		{
			if(i + ans[j][1] > n or i + ans[j][1] <= 0)
			{
				ok = 0;

				break;
			}

			if(i + ans[j][1] == 1) P1 = 1;

			if(i + ans[j][1] == n and P1 == -1) ok = 0;

			usado[i + ans[j][1]] = 1;
		}

		for(int j = 1; j <= n; j++)
			if(!usado[j]) ok = 0;

		if(ok)
		{
			for(int j = 1; j <= n; j++)
				answer(j, ans[j][1] + i);
			break;
		}
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:13:2: warning: assuming signed overflow does not occur when assuming that (X - c) > X is always false [-Wstrict-overflow]
  if(a >= b) return 0;
  ^~

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