Submission #881948

#	Time	Username	Problem	Language	Result	Execution time	Memory
881948		Alan	Xylophone (JOI18_xylophone)	C++17	100 / 100	43 ms	636 KiB

xylophone

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

int query(int s, int t);
void answer(int i, int a);

void solve(int N) {
	vector<int> ans (N+1);
	vector<bool> used (N+1);
	int l = 1, r = N;
	while (l+1 < r) {
		int mid = (l+r)/2;
		if (query(mid, N) == N-1) l = mid;
		else r = mid;
	}
	ans[l] = 1;
	used[1] = true;
	if (l > 1) {
		ans[l-1] = ans[l] + query(l-1, l);
		used[ans[l-1]] = true;
	}
	if (l < N) {
		ans[l+1] = ans[l] + query(l, l+1);
		used[ans[l+1]] = true;
	}
	for (int i = l-2; i > 0; i--) {
		int q = query(i, i+1);
		if (ans[i+1] + q > N || used[ans[i+1] + q]) ans[i] = ans[i+1] - q;
		else if (ans[i+1] - q < 1 || used[ans[i+1] - q]) ans[i] = ans[i+1] + q;
		else {
			int q2 = query(i, i+2);
			ans[i] = ans[i+1] - q;
			if (abs(ans[i] - ans[i+1]) != q || max({ans[i], ans[i+1], ans[i+2]}) - min({ans[i], ans[i+1], ans[i+2]}) != q2) ans[i] = ans[i+1] + q;
		}
		used[ans[i]] = true;
	}
	for (int i = l+2; i <= N; i++) {
		int q = query(i-1, i);
		if (ans[i-1] + q > N || used[ans[i-1] + q]) ans[i] = ans[i-1] - q;
		else if (ans[i-1] - q < 1 || used[ans[i-1] - q]) ans[i] = ans[i-1] + q;
		else {
			int q2 = query(i-2, i);
			ans[i] = ans[i-1] - q;
			if (abs(ans[i] - ans[i-1]) != q || max({ans[i], ans[i-1], ans[i-2]}) - min({ans[i], ans[i-1], ans[i-2]}) != q2) ans[i] = ans[i-1] + q;
		}
		used[ans[i]] = true;
	}
	for (int i = 1; i <= N; i++) answer(i, ans[i]);
}

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