Submission #988977

#	Time	Username	Problem	Language	Result	Execution time	Memory
988977		Mr_Ph	Xylophone (JOI18_xylophone)	C++17	100 / 100	52 ms	1216 KiB

xylophone

#include "xylophone.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
static int ans[5000];
int v[5000];
void solve(int n) {
	int idx=-1;
	int l=1,r=n;
	int cnt=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int value=query(mid,n);
		cnt++;
		if(value!=(n-1))
		r=mid-1;
		else l=mid+1,idx=mid-1;
	}
	for(int i=1;i<n;i++)
		v[i]=query(i,i+1),cnt++;
	ans[idx]=1;
	if((idx-1)>=0)
		ans[idx-1]=v[idx]+1;
	if((idx+1)<n)
		ans[idx+1]=v[idx+1]+1;
	map<int,int>mp;
	mp[1]++;
	for(int i=idx-2;i>=0;i--)
	{
		if((ans[i+1]+v[i+1])>n)
		{
			ans[i]=ans[i+1]-v[i+1];
			mp[ans[i]]++;
			continue;
		}
		// cout<<"HI"<<endl;
		if((ans[i+1]-v[i+1])<=0)
		{
			ans[i]=v[i+1]+ans[i+1];
			mp[ans[i]]++;
			continue;
		}
		int a=ans[i+1],b=ans[i+2];
		int v1=v[i+1]+ans[i+1],v2=ans[i+1]-v[i+1];
		if(mp[v1])
		{
			ans[i]=v2;
			continue;
		}
		if(mp[v2])
		{
			ans[i]=v1;
			continue;
		}
		int value=query(i+1,i+3);
		cnt++;
		// cout<<i<<" "<<a<<" "<<b<<endl;
		if((v1!=a)&&(v1!=b)&&(v2!=a)&&(v2!=b))
			assert((max({a,b,v1})-min({a,b,v1}))!=((max({a,b,v2})-min({a,b,v2}))));
		if(((max({a,b,v1})-min({a,b,v1}))==value)&&(v1!=a)&&(v1!=b)&&(v1>0)&&(v1<=n))
			ans[i]=v1;
		else ans[i]=v2;
		mp[ans[i]]++;
	}
	// for(int i=0;i<n;i++)cout<<ans[i]<<" ";
	// cout<<endl;
	for(int i=idx+2;i<n;i++)
	{
		if((ans[i-1]+v[i])>n)
		{
			ans[i]=ans[i-1]-v[i];
			mp[ans[i]]++;
			continue;
		}
		if((ans[i-1]-v[i])<=0)
		{
			ans[i]=v[i]+ans[i-1];
			mp[ans[i]]++;
			continue;
		}
		int a=ans[i-1],b=ans[i-2];
		int v1=v[i]+ans[i-1],v2=ans[i-1]-v[i];
		if(mp[v1])
		{
			ans[i]=v2;
			continue;
		}
		if(mp[v2])
		{
			ans[i]=v1;
			continue;
		}
		int value=query(i-1,i+1);
		if((v1!=a)&&(v1!=b)&&(v2!=a)&&(v2!=b))
			assert((max({a,b,v1})-min({a,b,v1}))!=((max({a,b,v2})-min({a,b,v2}))));
		if(((max({a,b,v1})-min({a,b,v1}))==value)&&(v1!=a)&&(v1!=b))
			ans[i]=v1;
		else ans[i]=v2;
		mp[ans[i]]++;
	}
	// ans[0]=0;
	assert(cnt<=7500);
	for(int i=1;i<=n;i++){
		// cout<<ans[i-1]<<" ";
		answer(i,ans[i-1]);
	}
}

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