Submission #959604

#	Time	Username	Problem	Language	Result	Execution time	Memory
959604		LCJLY	Xylophone (JOI18_xylophone)	C++14	0 / 100	3046 ms	344 KiB

xylophone

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

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;

void solve(int n) {
	//find index of value 1
	int l=1;
	int r=n;
	int mid;
	int one=1;
	
	while(l<=r){
		mid=(l+r)/2;
		int hold=query(mid,n);
		if(hold==n-1){
			one=mid;
			l=mid+1;;
		}
		else r=mid-1;
	}
	
	int ans[n+5];
	memset(ans,-1,sizeof(ans));
	ans[one]=1;
	
	set<int>se;
	for(int x=2;x<=n;x++){
		se.insert(x);
	}
	
	//neighbour values
	if(one>1){
		ans[one-1]=1+query(one-1,one);
		se.erase(ans[one-1]);
	}
	if(one<n){
		ans[one+1]=1+query(one,one+1);
		se.erase(ans[one+1]);
	}
	
	int st=1;
	int ed=n;
	
	if(one==1){
		ed=n-1;
	}
	else st=2;
	
	//recover other values
	for(int x=one-2;x>=st;x--){
		int a=query(x,x+1);
		if(se.find(ans[x+1]+a)==se.end()&&se.find(ans[x+1]-a)!=se.end()){
			ans[x]=ans[x+1]-a;
			se.erase(ans[x]);
			continue;
		}
		if(se.find(ans[x+1]+a)!=se.end()&&se.find(ans[x+1]-a)==se.end()){
			ans[x]=ans[x+1]+a;
			se.erase(ans[x]);
			continue;
		}
			
		int b=query(x,x+2);
		int diff=abs(ans[x+1]-ans[x+2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else if(a==b){
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else if(a>b){
			if(ans[x+1]>ans[x+2]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		else{
			if(ans[x+2]>ans[x+1]){
				ans[x]=ans[x+1]-a;
			}
			else{
				ans[x]=ans[x+1]+a;
			}
		}
		se.erase(ans[x]);
	}	
	
	for(int x=one+2;x<=ed;x++){
		int a=query(x-1,x);
		if(se.find(ans[x-1]+a)==se.end()&&se.find(ans[x-1]-a)!=se.end()){
			ans[x]=ans[x-1]-a;
			se.erase(ans[x]);
			continue;
		}
		if(se.find(ans[x-1]+a)!=se.end()&&se.find(ans[x-1]-a)==se.end()){
			ans[x]=ans[x-1]+a;
			se.erase(ans[x]);
			continue;
		}
		int b=query(x-2,x);
		int diff=abs(ans[x-1]-ans[x-2]);
		if(b==diff&&a<b){
			//mid
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else if(a==b){
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else if(a>b){
			if(ans[x-1]>ans[x-2]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		else{
			if(ans[x-2]>ans[x-1]){
				ans[x]=ans[x-1]-a;
			}
			else{
				ans[x]=ans[x-1]+a;
			}
		}
		se.erase(ans[x]);
	}	
	
	for(int x=1;x<=n;x++){
		if(ans[x]!=-1){
			se.erase(se.find(ans[x]));
		}
	}

	for(int x=1;x<=n;x++){
		if(ans[x]==-1) ans[x]=*se.begin();
		answer(x,ans[x]);
	}
}

//code

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