Submission #283132

#	Time	Username	Problem	Language	Result	Execution time	Memory
283132		keta_tsimakuridze	Xylophone (JOI18_xylophone)	C++14	100 / 100	145 ms	572 KiB

xylophone

#include "xylophone.h"
#include<iostream>
	int ans[5005+5],val1[5005+4],val2[5005+4],mx,id1,id2,value[5005+4];

static int A[5000];

void solve(int N) {


	/*l=2; r=N;
	while(l<=r){
		int mid=(l+r)/2;
		if(query(mid,N)!=N-1){
			ind=mid-1; r=mid-1;
		}
		else l=mid+1;
	}
	ans[ind]=1;
	if(ind!=n) ans[ind+1]=query(ind,ind+1)+1;
	if(ind!=1) ans[ind-1]=query(ind,ind-1)+1;
	*/	
	 value[3]=query(1,2);

	ans[1]=0; ans[2]=value[3]; mx=value[3]; id1=1;id2=2;
	int mn=0;
	for(int k=3;k<=N;k++){	
	        val1[k]=query(k-2,k);
			val2[k]=query(k-1,k);
		if(ans[k-1]<ans[k-2]){
		
			if(val1[k]==value[k]) ans[k]=ans[k-1]+val2[k];
			else if(val1[k]==val2[k]) ans[k]=ans[k-1]+val2[k];
			else ans[k]=ans[k-1]-val2[k];
		}
		else {
			if(value[k]==val1[k] || val1[k]==val2[k]) ans[k]=ans[k-1]-val2[k];
			else ans[k]=ans[k-1]+val2[k];
		}
		value[k+1]=val2[k];
	if(ans[k]<mn)mn=ans[k],id1=k; 
	if(ans[k]>mx)mx=ans[k],id2=k;
	}	
	if(id1>id2){
		 mn=0; std::swap(ans[1],ans[2]);
			for(int k=3;k<=N;k++){	
		if(ans[k-1]<ans[k-2]){
		
			if(val1[k]==value[k]) ans[k]=ans[k-1]+val2[k];
			else if(val1[k]==val2[k]) ans[k]=ans[k-1]+val2[k];
			else ans[k]=ans[k-1]-val2[k];
		}
		else {
			if(value[k]==val1[k] || val1[k]==val2[k]) ans[k]=ans[k-1]-val2[k];
			else ans[k]=ans[k-1]+val2[k];
		}
		value[k+1]=val2[k];
	if(ans[k]<mn)mn=ans[k]; 
	}
	}
	for(int k=1;k<=N;k++){
		ans[k]+=1-mn; 
		answer(k,ans[k]);
	
	} 

	
}

Compilation message (stderr)

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

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