Submission #67426

#	Time	Username	Problem	Language	Result	Execution time	Memory
67426		aome	Xylophone (JOI18_xylophone)	C++17	100 / 100	90 ms	716 KiB

xylophone

#include "xylophone.h"

#include <bits/stdc++.h>

using namespace std;

int a[5005];
bool visit[5005];

void solve(int n) {
	int l = 1, r = n;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (query(mid, n) == n - 1) l = mid;
		else r = mid - 1;
	}
	int pos1 = l;
	a[pos1] = 1;
	visit[1] = 1;
	int tmp = 1 + query(pos1, pos1 + 1);
	a[pos1 + 1] = tmp;
	visit[tmp] = 1;
	for (int i = pos1 + 2; i <= n; ++i) {
		int tmp = query(i - 1, i);
		if (a[i - 1] + tmp > n || visit[a[i - 1] + tmp]) {
			a[i] = a[i - 1] - tmp;
		}
		else if (a[i - 1] - tmp < 1 || visit[a[i - 1] - tmp]) {
			a[i] = a[i - 1] + tmp;
		}
		else {
			int tmp2 = query(i - 2, i);
			a[i] = a[i - 1] + tmp;
			int mn = min(min(a[i], a[i - 1]), a[i - 2]);
			int mx = max(max(a[i], a[i - 1]), a[i - 2]);
			if (mx - mn != tmp2) a[i] = a[i - 1] - tmp;
		}
		visit[a[i]] = 1;
	}
	if (pos1 != 1) {
		int tmp = 1 + query(pos1 - 1, pos1);
		a[pos1 - 1] = tmp;
	}
	for (int i = pos1 - 2; i >= 1; --i) {
		int tmp = query(i, i + 1);
		if (a[i + 1] + tmp > n || visit[a[i + 1] + tmp]) {
			a[i] = a[i + 1] - tmp;
		}
		else if (a[i + 1] - tmp < 1 || visit[a[i + 1] - tmp]) {
			a[i] = a[i + 1] + tmp;
		}
		else {
			int tmp2 = query(i, i + 2);
			a[i] = a[i + 1] + tmp;
			int mn = min(min(a[i], a[i + 1]), a[i + 2]);
			int mx = max(max(a[i], a[i + 1]), a[i + 2]);
			if (mx - mn != tmp2) a[i] = a[i + 1] - tmp;
		}
		visit[a[i]] = 1;
	}
	for (int i = 1; i <= n; ++i) answer(i, a[i]);
}

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