Submission #374848

#	Time	Username	Problem	Language	Result	Execution time	Memory
374848		peijar	Xylophone (JOI18_xylophone)	C++17	47 / 100	122 ms	492 KiB

xylophone

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

static int A[5001];

// On peut avoir pos min en log(N) operations : 13 op

void calcRep(int deb, int fin, bool avant, bool estMin)
{
	if (deb > fin) return ;
	if (avant)
	{
		int diffMax = query(deb-1, fin);
		if (deb == fin)
		{
			A[deb] = estMin ? A[deb-1] + diffMax : A[deb-1] - diffMax;
			return ;
		}
		int lo(deb), up(fin);
		while (lo < up)
		{
			int mid = (lo + up) / 2;
			if (query(deb-1, mid) == diffMax)
				up = mid;
			else
				lo = mid+1;
		}
		A[lo] = estMin ? A[deb-1] + diffMax : A[deb-1] - diffMax;
		calcRep(deb, lo-1, false, !estMin);
		calcRep(lo+1, fin, true, !estMin);
	}
	else
	{
		int diffMax = query(deb, fin+1);
		if (deb == fin)
		{
			A[deb] = estMin ? A[deb+1] + diffMax : A[deb+1] - diffMax;
			return ;
		}
		int lo(deb), up(fin);
		while (lo < up)
		{
			int mid = (lo + up + 1) / 2;
			if (query(mid, fin+1) == diffMax)
				lo = mid;
			else
				up = mid-1;
		}
		A[lo] = estMin ? A[fin+1] + diffMax : A[fin+1] - diffMax;
		calcRep(deb, lo-1, false, !estMin);
		calcRep(lo+1, fin, true, !estMin);
	}
}

void solve(signed N) 
{
	int diffMax = N-1;
	
	int lo(1), up(N);
	while (lo < up)
	{
		int mid = (lo + up+1)/2;
		if (query(mid, N) == diffMax)
			lo = mid;
		else
			up = mid-1;
	}
	int posMin = lo;
	A[posMin] = 1;
	calcRep(1, posMin-1, false, true);
	calcRep(posMin+1, N, true, true);
	for (int i(1); i <= N; ++i)
		answer(i, A[i]);
}

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