제출 #533980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533980		michao	Xylophone (JOI18_xylophone)	C++14	47 / 100	99 ms	340 KiB

xylophone

#include "xylophone.h"
using namespace std;
const int MAX=5005;
int ans[MAX];
bool zajety[MAX];
int n;

bool check(int x){
	return x>=1 && x<=n && !zajety[x];
}

void solve(int N){
	n=N;
  int ip=1,ik=n;
  while (ip+1<ik){
		int mid=(ip+ik)>>1;
		if (query(1,mid)==n-1)ik=mid;
		else ip=mid;
  }
  int r=ik;
  ik=r,ip=1;
  while (ip+1<ik){
		int mid=(ip+ik)>>1;
		if (query(mid,r)==n-1)ip=mid;
		else ik=mid;
  }	
  int l=ip;
  ans[l]=1,ans[r]=n;
  zajety[1]=true;
  zajety[n]=true;
  for (int i=l-1;i>=1;i--){
		if (i==l-1){
			int probuj=query(i,l)+ans[l];
			ans[i]=probuj;
			zajety[ans[i]]=true;
		}
		else{
			int q1=query(i,i+1); // poprzedni
			int q2=query(i,i+2); // przedpoprzedni
			int a=ans[i+2];
			int b=ans[i+1];
			if (a<b){
				if (check(b+q1) && b+q1==q2+a){
					ans[i]=b+q1;
				}
				else ans[i]=b-q1;
			}
			else{
				if (check(b-q1) && b-q1==a-q2){
					ans[i]=b-q1;
				}
				else ans[i]=b+q1;
			}
		}
		zajety[ans[i]]=true;
  }
  
  
  for (int i=l+1;i<=r-1;i++){
		if (i==l+1){
			int probuj=query(l,i)+ans[l];
			ans[i]=probuj;
			zajety[ans[i]]=true;
		}
		else{
			int q1=query(i-1,i); // poprzedni
			int q2=query(i-2,i); // przedpoprzedni
			int a=ans[i-2];
			int b=ans[i-1];
			if (a<b){
				if (check(b+q1) && b+q1==q2+a){
					ans[i]=b+q1;
				}
				else ans[i]=b-q1;
			}
			else{
				if (check(b-q1) && b-q1==a-q2){
					ans[i]=b-q1;
				}
				else ans[i]=b+q1;
			}
		}
		zajety[ans[i]]=true;
  }
  
  for (int i=r+1;i<=n;i++){
		if (i==r+1){
			int probuj=ans[r]-query(r,i);
			ans[i]=probuj;
			zajety[ans[i]]=true;
		}
		else{
			int q1=query(i-1,i); // poprzedni
			int q2=query(i-2,i); // przedpoprzedni
			int a=ans[i-2];
			int b=ans[i-1];
			if (a<b){
				if (check(b+q1) && b+q1==q2+a){
					ans[i]=b+q1;
				}
				else ans[i]=b-q1;
			}
			else{
				if (check(b-q1) && b-q1==a-q2){
					ans[i]=b-q1;
				}
				else ans[i]=b+q1;
			}
		}
		zajety[ans[i]]=true;
  }
  for (int i=1;i<=n;i++)answer(i,ans[i]);
}

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