Submission #1116493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116493		pedroslrey	Xylophone (JOI18_xylophone)	C++17	100 / 100	194 ms	960 KiB

xylophone

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

using namespace std;

vector<int> to_perm(vector<int> &raw) {
	int mini = 1e9;
	for (int x: raw) 
		mini = min(mini, x);

	vector<int> ans;
	for (int x: raw)
		ans.push_back(x - mini + 1);

	return ans;
}

void solve(int n) {
	vector<int> delta;

	for (int i = 1; i < n; ++i) 
		delta.push_back(query(i, i + 1));

	vector<bool> sign{false};
	for (int i = 1; i < n - 1; ++i) {
		int t = query(i, i + 2);

		if (delta[i-1] + delta[i] == t) sign.push_back(sign.back());
		else sign.push_back(!sign.back());
	}

	vector<int> raw{0};
	for (int i = 0; i < n-1; ++i)
		raw.push_back(raw.back() + delta[i]*(sign[i] ? 1 : -1));

	auto ps = to_perm(raw);

	for (int &x: raw) x = -x;

	auto qs = to_perm(raw);

	bool ansp = true;
	for (int i = 0; i < n; ++i)
		if (ps[i] == 1) break;
		else if (ps[i] == n) {
			ansp = false;
			break;
		}

	if (ansp) {
		for (int i = 0; i < n; ++i)
			answer(i + 1, ps[i]);
		return;
	}
	for (int i = 0; i < n; ++i)
		answer(i + 1, qs[i]);
}

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