Submission #1256166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256166		gelastropod	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	540 KiB

xylophone

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

void solve(int N) {
	vector<int> pairwise;
	for (int i = 1; i < N; i++)
		pairwise.push_back(query(i, i + 1));
	vector<pair<int, int>> poss;
	poss.push_back({ 0, 0 });
	poss.push_back({ -pairwise[0], pairwise[0] });
	for (int i = 2; i < N; i++) {
		int res = query(i - 1, i + 1);
		if (res == pairwise[i - 2] + pairwise[i - 1]) {
			if (poss[i - 2].first < poss[i - 1].first) poss.push_back({ poss[i - 1].first + pairwise[i - 1], poss[i - 1].second - pairwise[i - 1] });
			else poss.push_back({ poss[i - 1].first - pairwise[i - 1], poss[i - 1].second + pairwise[i - 1] });
		}
		else {
			if (poss[i - 2].first < poss[i - 1].first) poss.push_back({ poss[i - 1].first - pairwise[i - 1], poss[i - 1].second + pairwise[i - 1] });
			else poss.push_back({ poss[i - 1].first + pairwise[i - 1], poss[i - 1].second - pairwise[i - 1] });
		}
	}
	pair<int, int> low = { 0, 0 };
	for (int i = 1; i < N; i++) low.first = min(low.first, poss[i].first), low.second = min(low.second, poss[i].second);
	for (int i = 0; i < N; i++) poss[i].first += 1 - low.first, poss[i].second += 1 - low.second;
	bool first = true, found = false;
	for (int i = 0; i < N; i++) {
		if (poss[i].first == 1) found = true;
		if (poss[i].first == N && !found) first = false;
	}
	for (int i = 0; i < N; i++)
		answer(i + 1, (first ? poss[i].first : poss[i].second));
}

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