제출 #1320362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320362		JuanJL	Xylophone (JOI18_xylophone)	C++20	100 / 100	20 ms	944 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i< b;i++)
#define mset(a,v) memset(a,v,sizeof(a))

using namespace std;
typedef long long ll;

static int A[5000];
bool is[50001];

ll n;

map<pair<ll,ll>,ll> qu;
ll newquery(ll l, ll r){
	if(qu[{l,r}]!=0) return qu[{l,r}];
	else return qu[{l,r}]=query(l,r);
}

bool used(ll x){
	if(x<1 || x>n) return true;
	else return is[x];
}

pair<bool,vector<ll>> newsolve(ll x, ll v){
	vector<ll> res(n+2);
	res[x]=v;

	if(v==n){
		if(x+1<=n) res[x+1]=n-newquery(x,x+1);
		if(x-1>=1) res[x-1]=n-newquery(x-1,x);
	}else{
		if(x+1<=n) res[x+1]=1+newquery(x,x+1);
		if(x-1>=1) res[x-1]=1+newquery(x-1,x);
	}

	ll nx = x+2;
	while(nx<=n){
		/*if(res[nx-2]<res[nx-1]){
			ll q1 = newquery(nx-2,nx-1);
			ll q2 = newquery(nx-1,nx);
			if(q1+q2>n-1){
				res[nx]=res[nx-1]-q2;
			}else{
				ll q3 = newquery(nx-2,nx);
				if(q1+q2==q3) res[nx]=res[nx-1]+q2;
				else res[nx]=res[nx-1]-q2;
			}
		}else{
			ll q1 = newquery(nx-2,nx-1);
			ll q2 = newquery(nx-1,nx);
			if(q1+q2>n-1){
				res[nx]=res[nx-1]+q2;
			}else{
				ll q3 = newquery(nx-2,nx);
				if(q1+q2==q3) res[nx]=res[nx-1]-q2;
				else res[nx]=res[nx-1]+q2;
			}
		}*/
		ll aux = 1; if(res[nx-2]>res[nx-1]) aux*=-1;
		ll q1 = newquery(nx-2,nx-1);
		ll q2 = newquery(nx-1,nx);
		if(q1+q2>n-1 || used(res[nx-1]+q2*aux)){
			res[nx]=res[nx-1]-q2*aux;
		}else if(used(res[nx-1]-q2*aux)){
			res[nx]=res[nx-1]+q2*aux;
		}else{
			ll q3 = newquery(nx-2,nx);
			if(q1+q2==q3) res[nx]=res[nx-1]+q2*aux;
			else res[nx]=res[nx-1]-q2*aux;
		}
		if(res[nx]<1 || res[nx]>n) return {false,res};
		is[res[nx]]=true;
		nx++;
	}

	nx=x-2;
	while(nx>=1){
		ll aux = 1;  if(res[nx+1]<res[nx+2]) aux*=-1;
		ll q1 = newquery(nx+1,nx+2);
		ll q2 = newquery(nx,nx+1);
		if(q1+q2>n-1 || used(res[nx+1]+q2*aux)){
			res[nx]=res[nx+1]-q2*aux;
		}else if(used(res[nx+1]-q2*aux)){
			res[nx]=res[nx+1]+q2*aux;
		}else{
			ll q3 = newquery(nx,nx+2);
			if(q1+q2==q3) res[nx]=res[nx+1]+q2*aux;
			else res[nx]=res[nx+1]-q2*aux;
		}
		if(res[nx]<1 || res[nx]>n) return {false,res};
		is[res[nx]]=true;
		nx--;
	}
	
	return {true,res};
}

void solve(int N) {

	n=N;
	mset(is,false);
	ll l=1; ll r=n;
	while(l<=r){
		ll mid = (l+r)/2;

		if(newquery(mid,n)<n-1) r=mid-1;
		else l=mid+1;
	}

	ll x = r;

	pair<bool,vector<ll>> res = newsolve(x,1);

	forn(i,0,n) answer(i+1,res.snd[i+1]);
	
	
}

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