Submission #881935

#	Time	Username	Problem	Language	Result	Execution time	Memory
881935		Alan	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	432 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+1;
	while (l+1 < r) {
		int mid = (l+r)/2;
		if (query(mid, N) == N-1) l = mid;
		else r = mid;
	}
	ans[l] = 1;
	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;
	}
	used[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);
			if (q2 == abs(ans[i+1] - ans[i+2])) ans[i] = ans[i+1] - q;
			else 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);
			if (q2 == abs(ans[i-1] - ans[i-2])) ans[i] = ans[i-1] - q;
			else ans[i] = ans[i-1] + q;
		}
		used[ans[i]] = true;
	}
	for (int i = 1; i <= N; i++) answer(i, ans[i]);
}

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