Submission #1150733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150733		brover29	Xylophone (JOI18_xylophone)	C++20	100 / 100	18 ms	540 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll a[5005],used[N],diff[N];
void solve(ll r,ll n){
	while(r<n){
		ll x=diff[r];
		if((a[r]+x<=n&&(!used[a[r]+x]))&&(a[r]-x>=1&&(!used[a[r]-x]))){
			ll k=query(r-1,r+1);
			if(k==max({a[r]+x,a[r],a[r-1]})-min({a[r]+x,a[r],a[r-1]})){
				a[r+1]=a[r]+x;
			}else{
				a[r+1]=a[r]-x;

			}
		}else{
			if(a[r]+x<=n&&(!used[a[r]+x])){
				a[r+1]=a[r]+x;
			}else a[r+1]=a[r]-x;
		}
		r++;
		used[a[r]]=1;
	}
}void solve1(ll l,ll n){
	while(l>1){
		ll x=diff[l-1];
		if((a[l]+x<=n&&(!used[a[l]+x]))&&(a[l]-x>=1&&(!used[a[l]-x]))){
			ll k=query(l-1,l+1);
			if(k==max({a[l]+x,a[l],a[l+1]})-min({a[l]+x,a[l],a[l+1]})){
				a[l-1]=a[l]+x;
			}else{
				a[l-1]=a[l]-x;

			}
		}else{
			if(a[l]+x<=n&&(!used[a[l]+x])){
				a[l-1]=a[l]+x;
			}else a[l-1]=a[l]-x;
		}
		l--;
		used[a[l]]=1;
	}
}
void solve(int n) {

	for(ll i=1;i<n;i++)diff[i]=query(i,i+1);
	ll l=1,r=n;
	while(l<r){
        ll mid=(r+l)>>1;
        if(query(1,mid)==n-1)r=mid;
        else l=mid+1;
	}
	a[l]=n;
	solve(l,n);
	solve1(l,n);
	for(ll i=1;i<=n;i++)answer(i,a[i]);
}

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