제출 #1311762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311762		madamadam3	Xylophone (JOI18_xylophone)	C++20	100 / 100	23 ms	664 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

void solve(int N) {
	int value = query(1, N);

	int L = 1, hi = N;
	while (L < hi) {
		int mid = L + (hi - L + 1) / 2;
		if (query(mid, N) == value) L = mid;
		else hi = mid - 1;
	}

	vector<int> ans(N+1, -1);
	set<int> avail; for (int i = 2; i <= N; i++) avail.insert(i);

	for (int idx = 0; idx < N; idx++) {
		int i = (L + idx <= N) ? L+idx : L - ((L+idx) - N);

		if (i == L) ans[i] = 1;
		else if (i == L+1) ans[i] = 1 + query(L, i);
		else if (i == L-1) ans[i] = 1 + query(i, L);
		else {
			int dx = i>L ? query(i-1, i) : query(i, i+1);
			int a = ans[i>L ? i-1 : i+1] + dx, b = ans[i>L ? i-1 : i+1] - dx;
			int x = ans[i>L ? i-2 : i+2], y = ans[i>L ? i-1 : i+1];

			if (!avail.count(a)) ans[i] = b;
			else if (!avail.count(b)) ans[i] = a;
			else {
				int dy = i>L ? query(i-2, i) : query(i, i+2);
				if (y < a && a < x && dy == x-y) ans[i] = a;
				else if (y < x && x < a && dy == a-y) ans[i] = a;
				else if (x < y && y < a && dy == a-x) ans[i] = a;
				else ans[i] = b;
			}
		}

		avail.erase(ans[i]);
		answer(i, ans[i]);
	}
}

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