Submission #115353

#	Time	Username	Problem	Language	Result	Execution time	Memory
115353		dndhk	Xylophone (JOI18_xylophone)	C++14	0 / 100	3 ms	384 KiB

xylophone

#include "xylophone.h"


int arr[5001];

int zero(int x){
	return (x>0)?x:-x;
}

void solve(int N) {
	int s = 1, e = N, m;
	while(s<e){
		m = (s+e)/2+1;
		if(query(m, N)==N-1)	s = m;
		else	e = m-1;
	}
	arr[s] = 1;
	if(s!=1){
		arr[s-1] = query(s-1, s) + 1;
	}
	for(int i=s-2; i>=1; i--){
		int t = query(i, i+2);
		if(t==zero(arr[i+1]-arr[i+2])){
			int k = query(i, i+1);
			if(arr[i+1]>arr[i+2]){
				arr[i] = arr[i+1] - k;
			}else{
				arr[i] = arr[i+1] + k;
			}
		}else{
			int k = query(i, i+1);
			if(arr[i+1]>arr[i+2]){
				arr[i] = arr[i+1] + k;
			}else{
				arr[i] = arr[i+1] - k;
			}
		}
	}
	if(s!=N){
		arr[s+1] = query(s, s+1) + 1;
	}
	for(int i=s+2; i<=N; i++){
		int t = query(i-2, i);
		if(t==zero(arr[i-1]- arr[i-2])){
			int k = query(i-1, i);
			if(arr[i-1]>arr[i-2]){
				arr[i] = arr[i-1] - k;
			}else{
				arr[i]= arr[i-1] + k;
			}
		}else{
			int k = query(i-1, i);
			if(arr[i-1]>arr[i-2]){
				arr[i] = arr[i-1]+k;
			}else{
				arr[i] = arr[i-1]-k;
			}
		}
	}
	for(int i=1; i<=N; i++){
		answer(i, arr[i]);
	}
}

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