제출 #239593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239593		cfalas	Xylophone (JOI18_xylophone)	C++14	47 / 100	77 ms	500 KiB

xylophone

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

int ans[100001] = {};
int used[100001] = {};

void solve(int N) {

	// Find 1
	int pos=0;
	int value=N-1;
	while(N-1==value){
		pos++;
		value = query(pos, N);
		//cout<<pos<<" "<<value<<endl;
	}
	pos--;
	ans[pos] = 1;
	ans[pos+1] = 1+query(pos, pos+1);
	if(pos>=2) ans[pos-1] = 1+query(pos-1, pos);
	bool inc=false;
	for(int i=pos+2;i<=N;i++){
		int p=query(i-1, i);
		if(ans[i-1]+p>N){
			ans[i] = ans[i-1]-p;
			inc = ans[i]<ans[i-1];
			continue;
		}
		else if(ans[i-1]-p<=0){
			ans[i] = ans[i-1]+p;
			inc = ans[i]<ans[i-1];
			continue;
		}
		int pp = query(i-2, i);
		if(inc){
			if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] + p;
			else ans[i] = ans[i-1]-p;
		}
		else{
			if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] - p;
			else ans[i] = ans[i-1]+p;
		}
		inc = ans[i]<ans[i-1];
		//cout<<i<<" "<<ans[i]<<endl;
	}
	inc = false;
	for(int i=pos-2;i>0;i--){
		int p=query(i, i+1);
		if(ans[i+1]+p>N && !used[ans[i+1]+p]){
			ans[i] = ans[i+1]-p;
		inc = ans[i]<ans[i+1];
			used[ans[i]] = true;
			continue;
		}
		else if(ans[i+1]-p<=0 && !used[ans[i+1]-p]){
			ans[i] = ans[i+1]+p;
		inc = ans[i]<ans[i+1];
			used[ans[i]] = true;
			continue;
		}
		int pp = query(i, i+2);
		if(inc){
			if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] + p;
			else ans[i] = ans[i+1]-p;
		}
		else{
			if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] - p;
			else ans[i] = ans[i+1]+p;
		}
		used[ans[i]] = true;
		inc = ans[i]<ans[i+1];
		//cout<<i<<" "<<ans[i]<<endl;
	}
	//cout<<endl;
	for(int i = 1; i <= N; i++) {
		//cout<<i<<" "<<ans[i]<<endl;
		answer(i, ans[i]);
	}


}

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