Submission #1016161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016161		vjudge1	Xylophone (JOI18_xylophone)	C++17	47 / 100	51 ms	600 KiB

xylophone

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

void solve(int N) {
	int a[N+1];
	memset(a, 0, sizeof(a));
	// binary search pos of 1
	int lower = 1, upper = N;
	while(upper-lower>1){
		int mid = (upper+lower)/2;
		int x = query(mid, N);
		if(x==N-1) lower = mid;
		else upper = mid;
	}
	int pos1 = lower;
	a[pos1] = 1;
	if(pos1<N){
		// go to right
		int prev = query(pos1, pos1+1);
		a[pos1+1] = 1 + prev;
		for (int i=pos1+1; i<N; i++){
			int next = query(i, i+1);
			if(a[i]+next>N) a[i+1] = a[i]-next;
			else if(a[i]-next<1) a[i+1] = a[i]+next;
			else{
				int cur = query(i-1, i+1);
				if(cur==prev+next){
					if(a[i]>a[i-1]) a[i+1] = a[i]+next;
					else a[i+1] = a[i]-next;
				}
				else{
					if(a[i]>a[i-1]) a[i+1] = a[i]-next;
					else a[i+1] = a[i]+next;
				}
			}
			prev = next;
		}
	}
	if(pos1>1){
		// go to left
		int prev = query(pos1-1, pos1);
		a[pos1-1] = 1 + prev;
		for (int i=pos1-1; i>1; i--){
			int next = query(i-1, i);
			if(a[i]+next>N) a[i-1] = a[i]-next;
			else if(a[i]-next<1) a[i-1] = a[i]+next;
			else{
				int cur = query(i-1, i+1);
				if(cur==prev+next){
					if(a[i]>a[i+1]) a[i-1] = a[i]+next;
					else a[i-1] = a[i]-next;
				}
				else{
					if(a[i]>a[i+1]) a[i-1] = a[i]-next;
					else a[i-1] = a[i]+next;
				}
			}
			prev = next;
		}
	}
	for (int i=1; i<=N; i++) answer(i, a[i]);
	return;
}

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