Submission #1220104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220104		akqxolotl	Xylophone (JOI18_xylophone)	C++20	100 / 100	24 ms	720 KiB

xylophone

#include "xylophone.h"
static int A[5000];
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
/*typedef pair<int,int> pii;
#define fi first
#define se second*/

void solve(int n) {
	
	int l=1,h=n;
	while(l<h-1){
		int m=(l+h)/2;
		//debug(m)
		int q=query(m,n);
		//debug(q)
		if(q<n-1)h=m;
		else l=m;
	}
	int a[n+1];
	int mi=l;
	//debug(mi)
	a[mi]=1;
	set<int> s={1};
	if(mi>1){a[mi-1]=query(mi-1,mi)+1;s.insert(a[mi-1]);}
	a[mi+1]=query(mi,mi+1)+1;
	s.insert(a[mi+1]);
	for(int i=mi-2;i>0;i--){
		//debug(1)
		int q1=query(i,i+1);
		int c1=a[i+1]+q1;
		int c2=a[i+1]-q1;
		if(s.find(c1)!=s.end()){
			s.insert(c2);
			a[i]=c2;
			continue;
		}else if(s.find(c2)!=s.end()){
			s.insert(c1);
			a[i]=c1;
			continue;
		}
		int q2=query(i,i+2);
		if(q1+abs(a[i+1]-a[i+2])==q2){//sorted order
			if(a[i+2]>a[i+1])a[i]=c2;//desc
			else a[i]=c1;
		}else{
			if(a[i+2]>a[i+1])a[i]=c1;
			else a[i]=c2;
		}
		s.insert(a[i]);
	}
	for(int i=mi+2;i<=n;i++){
		//debug(2)
		int q1=query(i-1,i);
		int c1=a[i-1]+q1;
		int c2=a[i-1]-q1;
		if(s.find(c1)!=s.end()){
			s.insert(c2);
			a[i]=c2;
			continue;
		}else if(s.find(c2)!=s.end()){
			s.insert(c1);
			a[i]=c1;
			continue;
		}
		int q2=query(i-2,i);
		if(q1+abs(a[i-1]-a[i-2])==q2){
			if(a[i-2]<a[i-1])a[i]=c1;//asc
			else a[i]=c2;
		}else{
			if(a[i-2]<a[i-1])a[i]=c2;
			else a[i]=c1;
		}
		s.insert(a[i]);
	}
	
	for(int i=1;i<=n;i++){
		
		//cerr<<a[i]<<' ';
		answer(i,a[i]);
	}
		
}

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