Submission #152732

#	Time	Username	Problem	Language	Result	Execution time	Memory
152732		junodeveloper	Xylophone (JOI18_xylophone)	C++14	100 / 100	97 ms	512 KiB

xylophone

#include "xylophone.h"

static int A[5010];
static bool used[5010]={0};
int n;
inline void Set(int i, int x) {
	A[i]=x;
	used[x]=1;
}
inline bool Poss(int x) {
	return 1<=x&&x<=n&&!used[x];
}
void solve(int N) {
	n=N;
	int lo=1, hi=N, x, y;
	while(lo<hi) {
		int mid=(lo+hi+1)/2;
		x=query(mid,N);
		if(x==N-1) lo=mid;
		else hi=mid-1;
	}
	Set(lo,1);
	int i;
	if(lo+1<=N) {
		x=query(lo,lo+1);
		Set(lo+1,x+1);
	}
	if(lo-1>=1) {
		x=query(lo-1,lo);
		Set(lo-1,x+1);
	}
	for(i=lo+2;i<=N;i++) {
		x=query(i-1,i);
		if(!Poss(A[i-1]+x)) {
			Set(i,A[i-1]-x);
		} else if(!Poss(A[i-1]-x)) {
			Set(i,A[i-1]+x);
		} else {
			if(A[i-2]>A[i-1]) {
				y=query(i-2,i);
				if(y==A[i-2]-A[i-1]+x) {
					Set(i,A[i-1]-x);
				} else {
					Set(i,A[i-1]+x);
				}
			} else {
				y=query(i-2,i);
				if(y==A[i-1]-A[i-2]+x) {
					Set(i,A[i-1]+x);
				} else {
					Set(i,A[i-1]-x);
				}
			}
		}
	}
	for(i=lo-2;i>=1;i--) {
		x=query(i,i+1);
		if(!Poss(A[i+1]+x)) {
			Set(i,A[i+1]-x);
		} else if(!Poss(A[i+1]-x)) {
			Set(i,A[i+1]+x);
		} else {
			if(A[i+2]>A[i+1]) {
				y=query(i,i+2);
				if(y==A[i+2]-A[i+1]+x) {
					Set(i,A[i+1]-x);
				} else {
					Set(i,A[i+1]+x);
				}
			} else {
				y=query(i,i+2);
				if(y==A[i+1]-A[i+2]+x) {
					Set(i,A[i+1]+x);
				} else {
					Set(i,A[i+1]-x);
				}
			}
		}
	}
	for(i=1;i<=N;i++) answer(i,A[i]);
}

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