Submission #1265266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265266		Bahamin	Xylophone (JOI18_xylophone)	C++20	100 / 100	344 ms	98252 KiB

xylophone

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

using namespace std;

static int A[5000];

void solve(int n) {
	int dis[n][n];
	for (int i = 0; i < n - 1; i++) dis[i][i + 1] = query(i + 1, i + 2);
	for (int i = 0; i < n - 2; i++) 
	{
		dis[i][i + 2] = query(i + 1, i + 3);
		if (dis[i][i + 2] == dis[i][i + 1]) dis[i][i + 2] = dis[i][i + 1] - dis[i + 1][i + 2];
		else if (dis[i][i + 2] == dis[i + 1][i + 2]) dis[i][i + 2] = dis[i + 1][i + 2] - dis[i][i + 1];
	}
	for (int i = 3; i < n; i++)
	{
		for (int l = 0; l < n - i; l++)
		{
			int r = l + i;
			if (dis[l][l + 1] + dis[l][l + 2] == dis[l + 1][l + 2])
			{
				if (dis[l + 1][r] + dis[l + 2][r] == dis[l + 1][l + 2]) dis[l][r] = abs(dis[l][l + 1] - dis[l + 1][r]);
				else 
				{
					if (dis[l + 1][r] < dis[l + 2][r]) dis[l][r] = dis[l + 1][r] + dis[l][l + 1];
					else dis[l][r] = dis[l + 2][r] + dis[l][l + 2];
				}
			} else 
			{	
				if (dis[l + 1][r] + dis[l + 2][r] == dis[l + 1][l + 2]) 
				{
					if (dis[l][l + 1] < dis[l][l + 2]) dis[l][r] = dis[l][l + 1] + dis[l + 1][r];
					else dis[l][r] = dis[l][l + 2] + dis[l + 2][r];
				}
				else 
				{
					if (dis[l][l + 1] < dis[l][l + 2])
					{
						if (dis[l + 1][r] < dis[l + 2][r]) dis[l][r] = abs(dis[l + 1][r] - dis[l][l + 1]);
						else dis[l][r] = dis[l][l + 1] + dis[l + 2][r] + dis[l + 1][l + 2];
					} else 
					{
						if (dis[l + 2][r] < dis[l + 1][r]) dis[l][r] = abs(dis[l + 2][r] - dis[l][l + 2]);
						else dis[l][r] = dis[l][l + 2] + dis[l + 1][r] + dis[l + 1][l + 2];
					}
				}
			}
		}
	}
	int ind = -1;
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (dis[i][j] == n - 1) ind = i, answer(i + 1, 1);
	for (int i = 0; i < n; i++) if (i != ind) answer(i + 1, dis[min(ind, i)][max(ind, i)] + 1);
}

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