Submission #209826

#	Time	Username	Problem	Language	Result	Execution time	Memory
209826		amiratou	Xylophone (JOI18_xylophone)	C++14	100 / 100	72 ms	636 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];
set<int> used;
void solve(int N) {

	int pos=N;
	int l=0,r=N-1;
	while(l<=r){
		int med=(l+r)>>1;
		if(query(med+1,N)!=(N-1))
			r=med-1;
		else l=med+1,pos=med;
	}
	used.insert(1);
	A[pos]=1;
	answer(pos+1,1);
	for (int i = pos-1; i >= 0; i--)
	{
		int d=query(i+1,i+2);//i-1
		int a=A[i+1]+d,b=A[i+1]-d;
		if((a<=0)||(a>N)||used.find(a)!=used.end()){A[i]=b,used.insert(b),answer(i+1,b);continue;}
		if((b<=0)||(b>N)||used.find(b)!=used.end()){A[i]=a,used.insert(a),answer(i+1,a);continue;}
		int h=query(i+1,i+3),val;
		if(h!=(abs(A[i+1]-A[i+2])+d)){
			if(A[i+1]<A[i+2])val=a;
			else val=b;
		}
		else{
			if(A[i+1]<A[i+2])val=b;
			else val=a;
		}
		A[i]=val;
		used.insert(val);
		answer(i+1,val);
	}
	for (int i = pos+1; i < N; i++)
	{
		int d=query(i,i+1);//i-1
		int a=A[i-1]+d,b=A[i-1]-d;
		if((a<=0)||(a>N)||used.find(a)!=used.end()){A[i]=b,used.insert(b),answer(i+1,b);continue;}
		if((b<=0)||(b>N)||used.find(b)!=used.end()){A[i]=a,used.insert(a),answer(i+1,a);continue;}
		int h=query(i-1,i+1),val;
		if(h!=(abs(A[i-2]-A[i-1])+d)){
			if(A[i-2]<A[i-1])val=b;
			else val=a;
		}
		else{
			if(A[i-2]<A[i-1])val=a;
			else val=b;
		}
		A[i]=val;
		used.insert(val);
		answer(i+1,val);
	}

}

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