Submission #170715

#	Time	Username	Problem	Language	Result	Execution time	Memory
170715		nafis_shifat	Xylophone (JOI18_xylophone)	C++14	100 / 100	81 ms	524 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
const int mxn=5001;
 int a[mxn];
int ek;
int cnt[mxn]={};
void solve(int N)
{

	int k;
	int lo=1;
	int hi=N;
	while(lo<=hi)
	{
		int mid=lo+hi>>1;

		if(query(mid,N)==N-1)
		{
			lo=mid+1;
		}
		else
		{
			k=mid;
			hi=mid-1;
		}

	}

	a[k-1]=1;
	cnt[1]=1;
	ek=k-1;



	for(int i=ek-1;i>0;i--)
	{
		k=query(i,i+1);

		if(a[i+1]-k<=0 || cnt[a[i+1]-k]==1)
		{
			a[i]=a[i+1]+k;
			cnt[a[i+1]+k]=1;
		}

		else if(a[i+1]+k>N || cnt[a[i+1]+k]==1)
		{
			a[i]=a[i+1]-k;
			cnt[a[i+1]-k]=1;
		}

		else
		{
			int tmp=query(i,i+2);

			if(max(a[i+1]+k,a[i+2])-min(a[i+1],a[i+2])==tmp)
			{
				a[i]=a[i+1]+k;
				cnt[a[i+1]+k]=1;
			}
			else
			{
				a[i]=a[i+1]-k;
				cnt[a[i+1]-k]=1;
			}
		}

	}


	for(int i=ek+1;i<=N;i++)
	{
	   
		k=query(i-1,i);

		if(a[i-1]-k<=0 || cnt[a[i-1]-k]==1)
		{
			a[i]=a[i-1]+k;
			cnt[a[i-1]+k]=1;
		}

		else if(a[i-1]+k>N || cnt[a[i-1]+k]==1)
		{
			a[i]=a[i-1]-k;
			cnt[a[i-1]-k]=1;
		}

		else
		{
			int tmp=query(i-2,i);

			if(max(a[i-1]+k,a[i-2])-min(a[i-1],a[i-2])==tmp)
			{
				a[i]=a[i-1]+k;
				cnt[a[i-1]+k]=1;
			}
			else
			{
				a[i]=a[i-1]-k;
				cnt[a[i-1]-k]=1;
			}
		}

	}



	



	for(int i = 1; i <= N; i++)
	{
	    answer(i,a[i]);
	
	}

}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:16:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
xylophone.cpp:36:10: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(int i=ek-1;i>0;i--)
          ^

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