Submission #239596

#	Time	Username	Problem	Language	Result	Execution time	Memory
239596		cfalas	Xylophone (JOI18_xylophone)	C++14	100 / 100	65 ms	536 KiB

xylophone

#include<bits/stdc++.h>
using namespace std;
#include "xylophone.h"

int ans[100001] = {};
int used[100001] = {};
#define MID ((l+r)/2)

void solve(int N) {

	// Find 1
	int pos=0;
	int l=1, r=N-1;
	int mm=-1;
	while(l<=r){
		//cout<<MID<<" "<<N<<endl;
		int q = query(MID, N);
		if(q==N-1) mm=MID, l = MID+1;
		else r = MID-1;
	}

	pos=mm;
	//cout<<pos<<endl;
	ans[pos] = 1;
	used[1] = true;
	ans[pos+1] = 1+query(pos, pos+1);
	used[ans[pos+1]] = true;
	if(pos>=2) ans[pos-1] = 1+query(pos-1, pos), used[ans[pos-1]]=true;
	bool inc=false;
	for(int i=pos+2;i<=N;i++){
		int p=query(i-1, i);
		if(ans[i-1]+p>N || used[ans[i-1]+p]){
			ans[i] = ans[i-1]-p;
			used[ans[i]] = true;
			inc = ans[i]<ans[i-1];
			continue;
		}
		else if(ans[i-1]-p<=0 || used[ans[i-1]-p]){
			ans[i] = ans[i-1]+p;
			used[ans[i]] = true;
			inc = ans[i]<ans[i-1];
			continue;
		}
		int pp = query(i-2, i);
		if(inc){
			if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] + p;
			else ans[i] = ans[i-1]-p;
		}
		else{
			if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] - p;
			else ans[i] = ans[i-1]+p;
		}
		inc = ans[i]<ans[i-1];
		used[ans[i]] = true;
		//cout<<i<<" "<<ans[i]<<endl;
	}
	inc = false;
	for(int i=pos-2;i>0;i--){
		int p=query(i, i+1);
		if(ans[i+1]+p>N || used[ans[i+1]+p]){
			ans[i] = ans[i+1]-p;
		inc = ans[i]<ans[i+1];
			used[ans[i]] = true;
			continue;
		}
		else if(ans[i+1]-p<=0 || used[ans[i+1]-p]){
			ans[i] = ans[i+1]+p;
		inc = ans[i]<ans[i+1];
			used[ans[i]] = true;
			continue;
		}
		int pp = query(i, i+2);
		if(inc){
			if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] + p;
			else ans[i] = ans[i+1]-p;
		}
		else{
			if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] - p;
			else ans[i] = ans[i+1]+p;
		}
		used[ans[i]] = true;
		inc = ans[i]<ans[i+1];
		//cout<<i<<" "<<ans[i]<<endl;
	}
	//cout<<endl;
	for(int i = 1; i <= N; i++) {
		//cout<<i<<" "<<ans[i]<<endl;
		answer(i, ans[i]);
	}


}

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