Submission #565843

#	Time	Username	Problem	Language	Result	Execution time	Memory
565843		1zaid1	Xylophone (JOI18_xylophone)	C++17	0 / 100	1 ms	208 KiB

xylophone

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

// static int A[5000];
struct range {int l, r, k, x, mx;};

void solve(int n) {
	vector<int> ans(n+10, 0);
	queue<range> q;
	for (int i = n; i >= 2; i--) {
		int y = (i-1==1?0:query(1, i-1));
		if (y != n-1) {
			q.push({1, i, 1, n, 1});
			if (i != n) q.push({i, n, 0, n, 1});
			ans[i] = n;
			break;
		}
	}

	
	while (!q.empty()) {
		auto [l, r, k, x, mx] = q.front(); q.pop();
		int dif = query(l, r);
		if (k) {
			for (int i = l; i < r; i++) {
				int y = (i+1==r?0:query(i+1, r));
				if (y != dif) {
					if (mx) ans[i] = x-dif;
					else ans[i] = x+dif;

					int m = (l+r)/2;
					if (m+1 != r) q.push({m+1, r, k, x, mx});
					if (i != m) q.push({i, m, !k, ans[i], !mx});
					if (l != i) q.push({l, i, k, ans[i], !mx});
					break;
				}
			}
		} else {
			for (int i = r; i > l; i--) {
				int y = (i-1==l?0:query(l, i-1));
				if (y != dif) {
					if (mx) ans[i] = x-dif;
					else ans[i] = x+dif;

					int m = (l+r)/2;
					if (m != l) q.push({l, m, k, x, mx});
					if (m+1 != i) q.push({m+1, i, !k, ans[i], !mx});
					if (i != r) q.push({i, r, k, ans[i], !mx});
					break;
				}
			}
		}
	}

	// for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl;
	for (int i = 1; i <= n; i++) answer(i, ans[i]);
}

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