Submission #58798

#	Time	Username	Problem	Language	Result	Execution time	Memory
58798		TadijaSebez	Xylophone (JOI18_xylophone)	C++11	100 / 100	82 ms	708 KiB

xylophone

#include "xylophone.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N=5050;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
//-----------------------//
/*
int _a[N],_b[N];
int _N;
int query(int l, int r)
{
	int Max=0,Min=_N+1,i;
	for(i=l;i<=r;i++) Max=max(Max,_a[i]),Min=min(Min,_a[i]);
	return Max-Min;
}
void answer(int i, int x){ _b[i]=x;}
*/
//-----------------------//
int sol[N];
bool was[N];
int abs(int x){ return x>0?x:-x;}
void solve(int n)
{
	int top=n-1,bot=2,mid,ans=1;
	while(top>=bot)
	{
		mid=top+bot>>1;
		if(query(mid,n)==n-1) ans=mid,bot=mid+1;
		else top=mid-1;
	}
	int i,cnt=0,j;
	sol[ans]=1;was[1]=1;cnt++;
	sol[ans+1]=query(ans,ans+1)+1;was[sol[ans+1]]=1;cnt++;
	if(ans!=1) sol[ans-1]=query(ans-1,ans)+1,was[sol[ans-1]]=1,cnt++;
	for(i=ans+2;i<=n;i++)
	{
		if(cnt==n-1)
		{
			for(j=1;j<=n;j++) if(!was[j]) break;
			sol[i]=j;
			was[j]=1;
			cnt++;
		}
		else
		{
			if(sol[i-1]<sol[i-2])
			{
				int q1=query(i-1,i);
				int d=abs(sol[i-1]-sol[i-2]);
				int h=sol[i-1];
				if(h-q1<=0 || was[h-q1])
				{
					sol[i]=h+q1;
					was[h+q1]=1;
					cnt++;
				}
				else if(h+q1>n || was[h+q1])
				{
					sol[i]=h-q1;
					was[h-q1]=1;
					cnt++;
				}
				else
				{
					int q2=query(i-2,i);
					if(q2==q1+d)
					{
						sol[i]=h-q1;
						was[h-q1]=1;
						cnt++;
					}
					else
					{
						sol[i]=h+q1;
						was[h+q1]=1;
						cnt++;
					}
				}
			}
			else
			{
				int q1=query(i-1,i);
				int d=abs(sol[i-1]-sol[i-2]);
				int h=sol[i-1];
				if(h-q1<=0 || was[h-q1])
				{
					sol[i]=h+q1;
					was[h+q1]=1;
					cnt++;
				}
				else if(h+q1>n || was[h+q1])
				{
					sol[i]=h-q1;
					was[h-q1]=1;
					cnt++;
				}
				else
				{
					int q2=query(i-2,i);
					if(q2==q1+d)
					{
						sol[i]=h+q1;
						was[h+q1]=1;
						cnt++;
					}
					else
					{
						sol[i]=h-q1;
						was[h-q1]=1;
						cnt++;
					}
				}
			}
		}
	}
	for(i=ans-2;i>=1;i--)
	{
		if(cnt==n-1)
		{
			for(j=1;j<=n;j++) if(!was[j]) break;
			sol[i]=j;
			was[j]=1;
			cnt++;
		}
		else
		{
			if(sol[i+1]<sol[i+2])
			{
				int q1=query(i,i+1);
				int d=abs(sol[i+1]-sol[i+2]);
				int h=sol[i+1];
				if(h-q1<=0 || was[h-q1])
				{
					sol[i]=h+q1;
					was[h+q1]=1;
					cnt++;
				}
				else if(h+q1>n || was[h+q1])
				{
					sol[i]=h-q1;
					was[h-q1]=1;
					cnt++;
				}
				else
				{
					int q2=query(i,i+2);
					if(q2==q1+d)
					{
						sol[i]=h-q1;
						was[h-q1]=1;
						cnt++;
					}
					else
					{
						sol[i]=h+q1;
						was[h+q1]=1;
						cnt++;
					}
				}
			}
			else
			{
				int q1=query(i,i+1);
				int d=abs(sol[i+1]-sol[i+2]);
				int h=sol[i+1];
				if(h-q1<=0 || was[h-q1])
				{
					sol[i]=h+q1;
					was[h+q1]=1;
					cnt++;
				}
				else if(h+q1>n || was[h+q1])
				{
					sol[i]=h-q1;
					was[h-q1]=1;
					cnt++;
				}
				else
				{
					int q2=query(i,i+2);
					if(q2==q1+d)
					{
						sol[i]=h+q1;
						was[h+q1]=1;
						cnt++;
					}
					else
					{
						sol[i]=h-q1;
						was[h-q1]=1;
						cnt++;
					}
				}
			}
		}
	}
	for(i=1;i<=n;i++) answer(i,sol[i]);
}
//-----------------------//
/*
int main()
{
	int i;
	scanf("%i",&_N);
	for(i=1;i<=_N;i++) scanf("%i",&_a[i]);
	solve(_N);
	for(i=1;i<=_N;i++) printf("%i ",_b[i]);
	printf("\n");
	return 0;
}
*/
//-----------------------//

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:30:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~

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