Submission #959583

#	Time	Username	Problem	Language	Result	Execution time	Memory
959583		LCJLY	Xylophone (JOI18_xylophone)	C++14	47 / 100	49 ms	688 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;

static int A[5000];

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);
		//show2(mid,mid,hold,hold);
		if(hold==n-1){
			one=mid;
			l=mid+1;;
		}
		else r=mid-1;
	}
	
	//show(one,one);
	
	int ans[n+5];
	memset(ans,-1,sizeof(ans));
	ans[one]=1;
	
	//neighbour values
	if(one>1){
		ans[one-1]=1+query(one-1,one);
	}
	if(one<n){
		ans[one+1]=1+query(one,one+1);
	}
	
	//recover other values
	for(int x=one-2;x>=1;x--){
		int a=query(x,x+1);
		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;
			}
		}
	}	
	
	for(int x=one+2;x<=n;x++){
		int a=query(x-1,x);
		int b=query(x-2,x);
		int diff=abs(ans[x-1]-ans[x-2]);
		//show3(x,x,a,a,b,b);
		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){
			//show3(x,x,a,a,b,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;
			}
		}
	}	
	

	//show4(ans,ans);
	
	for(int x=1;x<=n;x++){
		answer(x,ans[x]);
	}
}

//code

Compilation message (stderr)

xylophone.cpp:12:12: warning: 'A' defined but not used [-Wunused-variable]
   12 | static int A[5000];
      |            ^

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