Submission #1290651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290651		hasandas	Xylophone (JOI18_xylophone)	C++20	0 / 100	2 ms	332 KiB

xylophone

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

using namespace std;


void solve(int N) {
	vector<int> ans(N + 1, 0);

	int LJ = 1, HJ = N;
	while (LJ < HJ) {
		int mid = (LJ + HJ + 1) / 2;
		int q = query(mid, N);
		if (q == N - 1) {
			LJ = mid;
		}
		else {
			HJ = mid - 1;
		}
	}
	int pos1 = LJ;
	ans[pos1] = 1;

	int current_max = 1;
	int idx_max = pos1;
	for (int i = pos1 + 1; i <= N; ++i) {
		int q = query(pos1, i);
		if (q > current_max - 1) {
			ans[i] = q + 1;
			current_max = ans[i];
			idx_max = i;
		}
		else {
			int s = min(idx_max, i);
			int t = max(idx_max, i);
			int d = query(s, t);
			ans[i] = current_max - d;
		}
	}

	current_max = 1;
	idx_max = pos1;
	for (int i = pos1 - 1; i >= 1; --i) {
		int q = query(i, pos1);
		if (q > current_max - 1) {
			ans[i] = q + 1;
			current_max = ans[i];
			idx_max = i;
		}
		else {
			int s = min(idx_max, i);
			int t = max(idx_max, i);
			int d = query(s, t);
			ans[i] = current_max - d;
		}
	}

	for (int i = 1; i <= N; ++i) {
		answer(i, ans[i]);
	}
}

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