제출 #1150554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150554		brover29	Xylophone (JOI18_xylophone)	C++20	0 / 100	0 ms	432 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(int n) {
	ll l,r;
	for(ll i=1;i<n;i++){
		ll x=query(i,i+1);
		diff[i]=x;
		if(x==n-1){
			a[i]=1;
			used[1]=1;
			used[n]=1;
			a[i+1]=n;
			l=i;
			r=i+1;
		}
	}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);
			ll x1=a[r]+x;
			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++;
	}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);
			ll x1=a[l]+x;
			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--;
	}for(ll i=1;i<=n;i++)answer(i,a[i]);
}

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