제출 #285756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285756		Pyqe	Xylophone (JOI18_xylophone)	C++14	100 / 100	75 ms	632 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

long long n,sq[5069];
bitset<5069> vtd;

bool vld(long long x)
{
	return x>0&&x<=n&&!vtd[x];
}

void fl(long long lh,long long rh,long long u)
{
	long long i,k,l;
	
	for(i=lh;i!=rh+u;i+=u)
	{
		k=query(min(i,i-u),max(i,i-u));
		if(!vld(sq[i-u]-k))
		{
			sq[i]=sq[i-u]+k;
		}
		else if(!vld(sq[i-u]+k))
		{
			sq[i]=sq[i-u]-k;
		}
		else
		{
			l=query(min(i,i-u*2),max(i,i-u*2));
			if(max(sq[i-u]+k,sq[i-u*2])-min(sq[i-u],sq[i-u*2])==l)
			{
				sq[i]=sq[i-u]+k;
			}
			else
			{
				sq[i]=sq[i-u]-k;
			}
		}
		vtd[sq[i]]=1;
	}
}

void solve(int on)
{
	long long i,lh,rh,md,zz,st,fn;
	
	n=on;
	zz=1;
	for(lh=2,rh=n-1;lh<=rh;)
	{
		md=(lh+rh)/2;
		if(query(md,n)==n-1)
		{
			zz=md;
			lh=md+1;
		}
		else
		{
			rh=md-1;
		}
	}
	st=zz;
	sq[st]=1;
	vtd[1]=1;
	zz=n;
	for(lh=st+1,rh=n-1;lh<=rh;)
	{
		md=(lh+rh)/2;
		if(query(1,md)==n-1)
		{
			zz=md;
			rh=md-1;
		}
		else
		{
			lh=md+1;
		}
	}
	fn=zz;
	sq[fn]=n;
	vtd[n]=1;
	fl(st-1,1,-1);
	fl(st+1,fn-1,1);
	fl(fn+1,n,1);
	for(i=1;i<=n;i++)
	{
		answer(i,sq[i]);
	}
}

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