제출 #764606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764606		cheat_when_I_was_young	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 ms	208 KiB

xylophone

#include "xylophone.h"
using namespace std;
const int MN=5e3+5;

int arr[MN],ans[MN];
bool check[MN];
bool check2[MN];
int limit;
void solve(int n){
	if(n==1){
		answer(1,1); return;
	}
	for(int i=1;i<=n;++i){
		check2[i]=false;
	}
	limit=10000;
	int l=1,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		int res=query(mid,n); --limit;
		if(res==n-1) l=mid+1;
		else r=mid;
	}
	int idx=l-1;
	answer(idx,1);
	check2[1]=true;
	l=idx-2; r=idx+2;
	
	if(idx>1){
		int res=query(idx-1,idx); --limit;
		answer(idx-1,res+1);
		check2[res+1]=true;
	}
	int res=query(idx,idx+1); --limit;
	answer(idx+1,res+1);
	check2[res+1]=true;
	
	for(int i=l;i>=1;--i){
		int res=query(i,i+1); --limit;
		if(arr[i+1]+res>=n||arr[i+1]+res<=1||check2[arr[i+1]+res]){
			answer(i,arr[i+1]-res);
			check2[arr[i+1]-res]=true; continue;
		}
		if(arr[i+1]-res>=n||arr[i+1]-res<=1||check2[arr[i+1]-res]){
			answer(i,arr[i+1]+res);
			check2[arr[i+1]+res]=true; continue;
		}
		if(limit==i-1+(n-r+1)){
			if(!check2[arr[i+1]+res]&&arr[i+1]+res<n){
				answer(i,arr[i+1]+res);
				check2[arr[i+1]+res]=true;
			}
			else{
				answer(i,arr[i+1]-res);
				check2[arr[i+1]-res]=true;
			}
		}
		else{
			int res2=query(i,i+2); --limit;
			if(res==res2){
				if(arr[i+2]<arr[i+1]) arr[i]=arr[i+1]-res;
				else arr[i]=arr[i+1]+res;
			}
			else{
				if(arr[i+1]>arr[i+2]){
					if(res2==arr[i+1]-arr[i+2]) arr[i]=arr[i+1]-res;
					else arr[i]=arr[i+1]+res;
				}
				else{
					if(res2==arr[i+2]-arr[i+1]) arr[i]=arr[i+1]+res;
					else arr[i]=arr[i+1]-res;
				}
			}
			answer(i,arr[i]); check2[arr[i]]=true;
		}
	}
	for(int i=r;i<=n;++i){
		int res=query(i-1,i); --limit;
		if(arr[i-1]+res>n||arr[i-1]+res<=1||check2[arr[i-1]+res]){
			answer(i,arr[i-1]-res);
			check2[arr[i-1]-res]=true; continue;
		}
		if(arr[i-1]-res>n||arr[i-1]-res<=1||check2[arr[i-1]-res]){
			answer(i,arr[i-1]+res);
			check2[arr[i-1]+res]=true; continue;
		}
		if(limit==n-i){
			if(!check2[arr[i-1]+res]&&arr[i-1]+res<=n){
				answer(i,arr[i-1]+res);
				check2[arr[i-1]+res]=true;
			}
			else{
				answer(i,arr[i-1]-res);
				check2[arr[i-1]-res]=true;
			}
		}
		else{
			int res2=query(i-2,i); --limit;
			if(res==res2){
				if(arr[i-2]<arr[i-1]) arr[i]=arr[i-1]-res;
				else arr[i]=arr[i-1]+res;
			}
			else{
				if(arr[i-2]<arr[i-1]){
					if(res2==arr[i-1]-arr[i-2]) arr[i]=arr[i-1]-res;
					else arr[i]=arr[i-1]+res;
				}
				else{
					if(res2==arr[i-2]-arr[i-1]) arr[i]=arr[i-1]+res;
					else arr[i]=arr[i-1]-res;
				}
			}
			answer(i,arr[i]); check2[arr[i]]=true;
		}
	}
}

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