Submission #170602

#	Time	Username	Problem	Language	Result	Execution time	Memory
170602		nafis_shifat	Xylophone (JOI18_xylophone)	C++14	0 / 100	2 ms	248 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,ek);

			if(abs(a[i+1]+k-a[ek])==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(ek,i);

			if(abs(a[i-1]+k-a[ek])==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: 0 / 11
• Subtask 2: 0 / 36
• Subtask 3: 0 / 53