제출 #408701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408701		AmineWeslati	Xylophone (JOI18_xylophone)	C++14	47 / 100	116 ms	1308 KiB

xylophone

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

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//-----------------------------------------------------------//

#define tt t

int N; 

const int MX=5e3+10;
unordered_map<int,int>mp[MX];

int get(int s, int t){
	if(!mp[s].count(t)) mp[s][t]=query(s,t);
	return mp[s][t];
}

int BS(){
	int l=1,r=N-1,ans=1;
	while(l<=r){
		int m=(l+r)/2;
		if(get(m,N)==N-1){
			ans=m; 
			l=m+1;
		}
		else r=m-1;
	}
	return ans; 
}

void solve(int N) {
	::N=N; 
	
	int idx=BS();

	vi a(N+1,-1); 
	
	//part 1
	a[idx]=1;
	a[idx+1]=get(idx,idx+1)+1;

	int prev=a[idx+1]-1,ty=0,s=idx; 
	FOR(t,idx+1,N){
		int x=get(s,t+1),y=get(t,t+1);
		if(!ty){
			if(x!=prev){
				if(x!=y) a[t+1]=a[t]+y;
				else a[t+1]=a[t]-y,ty=1,s=t; 
			}
			else a[t+1]=a[t]-y,ty=1,s=t; 
		}
		else{
			if(x!=prev){
				if(x!=y) a[t+1]=a[t]-y;
				else a[t+1]=a[t]+y,ty=0,s=t; 
			}
			else a[t+1]=a[t]+y,ty=0,s=t; 
		}
		prev=get(s,t+1);
	}

	//part 2

	if(idx>1){
		a[idx-1]=get(idx-1,idx)+1;

		prev=a[idx-1]-1,ty=0,s=idx; 
		ROF(t,2,idx){
			int x=get(t-1,s),y=get(t-1,t);
			if(!ty){
				if(x!=prev){
					if(x!=y) a[t-1]=a[t]+y;
					else a[t-1]=a[t]-y,ty=1,s=t; 
				}
				else a[t-1]=a[t]-y,ty=1,s=t; 
			}
			else{
				if(x!=prev){
					if(x!=y) a[t-1]=a[t]-y;
					else a[t-1]=a[t]+y,ty=0,s=t; 
				}
				else a[t-1]=a[t]+y,ty=0,s=t; 
			}
			prev=get(t-1,s);
		}

	}

	//FOR(i,1,N+1) cout << a[i] << ' '; cout << endl;

	FOR(i,1,N+1){
		answer(i,a[i]);
	}

}


/*

15
9 8 7 6 1 14 13 10 15 2 3 4 5 11 12

*/

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