Submission #654658

#	Time	Username	Problem	Language	Result	Execution time	Memory
654658		Tuanlinh123	Xylophone (JOI18_xylophone)	C++17	0 / 100	2 ms	208 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"
#define ll int
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;

ll a[10005];

void solve(ll n)
{
	ll Min=0;
	ll lo=1, hi=n, val=query(1, n);
	while (hi>lo)
	{
		ll mid=(hi+lo+1)/2;
		if (query(mid, n)!=val)
			hi=mid-1;
		else lo=mid;
	}
	Min=lo; a[Min]=1;
	if (Min!=1)
	{
		ll crr=Min, val=query(Min-1, Min);
		a[Min-1]=val+a[crr];
		bool Min_Max=0;
		// 0:Min, 1:Max
		for (ll i=Min-2; i>=1; i--)
		{
			ll val1=query(i, crr);
			if (!Min_Max)
			{
				if (val1!=val)
					a[i]=a[crr]+val1;
				else
				{
					crr=i+1; val1=query(i, crr);
					a[i]=a[crr]-val1;
					Min_Max^=1;
				}
			}
			else
			{
				if (val1!=val)
					a[i]=a[crr]-val1;
				else
				{
					crr=i+1; val1=query(i, crr);
					a[i]=a[crr]+val1;
					Min_Max^=1;
				}
			}
			val=val1;
		}
	}
	if (Min!=n)
	{
		ll crr=Min, val=query(Min, Min+1);
		a[Min+1]=val+a[crr];
		bool Min_Max=0;
		// 0:Min, 1:Max
		for (ll i=Min+2; i<=n; i++)
		{
			ll val1=query(crr, i);
			if (!Min_Max)
			{
				if (val1!=val)
					a[i]=a[crr]+val1;
				else
				{
					crr=i-1; val1=query(crr, i);
					a[i]=a[crr]-val1;
					Min_Max^=1;
				}
			}
			else
			{
				if (val1!=val)
					a[i]=a[crr]-val1;
				else
				{
					crr=i-1; val1=query(crr, i);
					a[i]=a[crr]+val1;
					Min_Max^=1;
				}
			}
			val=val1;
		}
	}
	for (ll i=1; i<=n; i++)
		answer(i, a[i]);
}

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