Submission #996059

#	Time	Username	Problem	Language	Result	Execution time	Memory
996059		cnn008	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	344 KiB

xylophone

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

int a[5005];

void solve(int n){
	int l=1,r=n,mn=1;
	while(l<=r){
		int mid=(l+r)/2;
		int val=query(mid,n);
		if(val==n-1){
			mn=mid;
			l=mid+1;
		}else r=mid-1;
	}
	a[mn]=1;
	if(mn<n) a[mn+1]=query(mn,mn+1)+1;
	for(int i=mn+2; i<=n; i++){
		int v=query(i-2,i);
		int l=query(i-1,i);
		if(v==max(a[i-1],a[i-2])-min(a[i-1],a[i-2])){
			if(a[i-1]>a[i-2]) a[i]=a[i-1]-l;
			else a[i]=a[i-1]+l;
		}else{
			int ifmin=a[i-1]-l;
			int ifmax=a[i-1]+l;
			if(ifmin>0 and max({a[i-2],a[i-1]}),ifmin==v) a[i]=ifmin;
			else a[i]=ifmax;
		}
	}
	if(mn>1) a[mn-1]=query(mn-1,mn)+1;
	for(int i=mn-2; i>=1; i--){
		int v=query(i,i+2);
		int l=query(i,i+1);
		if(v==max(a[i+1],a[i+2])-min(a[i+1],a[i+2])){
			if(a[i+1]>a[i+2]) a[i]=a[i+1]-l;
			else a[i]=a[i+1]+l;
		}else{
			int ifmin=a[i+1]-l;
			int ifmax=a[i+1]+l;
			if(max({a[i+2],a[i+1]})-ifmin==v) a[i]=ifmin;
			else a[i]=ifmax;
		}
	}
	for(int i=1; i<=n; i++) answer(i,a[i]);
	return;
}

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