제출 #1253559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253559		efex12	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	416 KiB

xylophone

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

using namespace std;

static int A[5000];

void solve(int N)
{
	int num=(N-1);
	int ans[N];
	int l=1,r=N;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(query(mid,N)==(N-1))
		{
			num=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	ans[num-1]=1;
	set<int> st;
	for(int i=2;i<=N;i++)
		st.insert(i);
	int a=num-1,b=num-1;
	if(num-1>=1)
		ans[num-2]=query(num-1,num)+1;
	if(num+1<=N)
		ans[num]=query(num,num+1)+1;
	while(a>=2||b<=(N-3))
	{
		if((a-2)>=0&&ans[a-1]==(*st.rbegin()))
		{
			ans[a-2]=ans[a-1]-query(a-1,a);
			a--;
			st.erase(ans[a]);
		}
		else if(b<=(N-3)&&ans[b+1]==(*st.rbegin()))
		{
			ans[b+2]=ans[b+1]-query(b+2,b+3);
			b++;
			st.erase(ans[b]);
		}
		else if(b<=(N-3))
		{
			int y=query(b+2,b+3);
			if(st.count(ans[b+1]-y)==0)
			{
				ans[b+2]=ans[b+1]+y;
				b++;
				st.erase(ans[b]);
				continue;
			}
			else if(st.count(ans[b+1]+y)==0)
			{
				ans[b+2]=ans[b+1]-y;
				b++;
				st.erase(ans[b]);
				continue;
			}
			int x=query(b+1,b+3);
			if(x==y||x==abs(ans[b+1]-ans[b]))
			{
				if(ans[b]>ans[b+1])
				{
					ans[b+2]=ans[b+1]-y;
					b++;
					st.erase(ans[b]);
					continue;
				}
				ans[b+2]=ans[b+1]+y;
				b++;
				st.erase(ans[b]);
				continue;
			}
			else
			{
				if(ans[b]>ans[b+1])
				{
					ans[b+2]=ans[b+1]+y;
					b++;
					st.erase(ans[b]);
					continue;
				}
				ans[b+2]=ans[b+1]-y;
				b++;
				st.erase(ans[b]);
				continue;
			}
		}
		else
		{
			int y=query(a-1,a);
			if(st.count(ans[a-1]-y)==0)
			{
				ans[a-2]=ans[a-1]+y;
				a--;
				st.erase(ans[a]);
				continue;
			}
			else if(st.count(ans[a-1]+y)==0)
			{
				ans[a-2]=ans[a-1]-y;
				a--;
				st.erase(ans[a]);
				continue;
			}
			int x=query(a-1,a+1);
			if(x==y||x==abs(ans[a-1]-ans[a]))
			{
				if(ans[a-1]>ans[a])
				{
					ans[a-2]=ans[a-1]-y;
					a--;
					st.erase(ans[a]);
					continue;
				}
				ans[a-2]=ans[a-1]+y;
				a--;
				st.erase(ans[a]);
				continue;
			}
			else
			{
				if(ans[a-1]>ans[a])
				{
					ans[a-2]=ans[a-1]+y;
					a--;
					st.erase(ans[a]);
					continue;
				}
				ans[a-2]=ans[a-1]-y;
				a--;
				st.erase(ans[a]);
				continue;
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		answer(i,ans[i-1]);
	}
	return;
}

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