Submission #111324

#	Time	Username	Problem	Language	Result	Execution time	Memory
111324		vex	Xylophone (JOI18_xylophone)	C++14	47 / 100	91 ms	428 KiB

xylophone

#include<bits/stdc++.h>
#include<xylophone.h>
using namespace std;
 
int a[5005];
bool bio[5005];
 
void solve(int n)
{
	int l=1;
	int r=n;
	int sol=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(query(1,mid)==n-1)
		{
			sol=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	
	for(int i=1;i<=n;i++)bio[i]=false;
	bio[n]=true;
	
	a[sol]=n;bio[n]=true;
	if(sol<n)a[sol+1]=n-query(sol,sol+1);
	a[sol-1]=n-query(sol-1,sol);
 
	for(int i=sol+2;i<=n;i++)
	{
		int maxx=max(a[i-1],a[i-2]);
		int minn=min(a[i-1],a[i-2]);
		int d1=query(i-2,i);
		if(d1==maxx-minn)
		{
			if(a[i-1]==maxx)a[i]=maxx-query(i-1,i);
			else a[i]=minn+query(i-1,i);
		}
		else
		{
			int br1=minn+d1;
			int br2=maxx-d1;
			if(br1>n || bio[br1])a[i]=br2;
			else if(br2<1 || bio[br2])a[i]=br1;
			else
			{
				int d2=query(i-1,i);
				int num1=a[i-1]-d2;
				int num2=a[i-1]+d2;
				
				if(num1>0 && num1<=n && (num1==br1 || num1==br2))a[i]=num1;
				else a[i]=num2;
			}
		}
		bio[a[i]]=true;
	}
	
	for(int i=sol-2;i>0;i--)
	{
		int maxx=max(a[i+1],a[i+2]);
		int minn=min(a[i+1],a[i+2]);
		int d1=query(i,i+2);
		if(d1==maxx-minn)
		{
			if(a[i+1]==maxx)a[i]=maxx-query(i,i+1);
			else a[i]=minn+query(i,i+1);
		}
		else
		{
			int br1=minn+d1;
			int br2=maxx-d1;
			if(br1>n || bio[br1])a[i]=br2;
			else if(br2<1 || bio[br2])a[i]=br1;
			else
			{
				int d2=query(i,i+1);
				int num1=a[i+1]-d2;
				int num2=a[i+1]+d2;
				
				if(num1<=n && num1>0 && (num1==br1 || num1==br2))a[i]=num1;
				else a[i]=num2;
			}
		}
		bio[a[i]]=true;
	}
	
	
	for(int i=1;i<=n;i++)answer(i,a[i]);
}

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