Submission #781057

#	Time	Username	Problem	Language	Result	Execution time	Memory
781057		sadsa	Xylophone (JOI18_xylophone)	C++17	100 / 100	264 ms	98768 KiB

xylophone

#include "xylophone.h"

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

using ll = long long;
using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;

constexpr int iINF = numeric_limits<int>::max();
constexpr ll lINF = numeric_limits<ll>::max();

template <typename T>
void DBG(T&& arg) {
    cerr << arg << '\n';
}

template <typename T, typename... Ts>
void DBG(T&& x, Ts&&... y) {
    cerr << x << ' ';
    DBG(y...);
}

static vector<vi> qcache;
int queries;

int q(int l, int r) {
	if (l > r) swap(l, r);

	int Q;

	if (l == r) Q = 0;
	else {
		if (qcache[l][r] == -1) queries++;
		Q = (qcache[l][r] != -1)? qcache[l][r]: (qcache[l][r] = query(l, r));
	}

	DBG("query:", l, r, "V:", Q);

	return Q;
}

// finds a2
int get_next(int a0, int a1, int q02, int q12) {
	int a2;

	int q01 = abs(a1 - a0);

	if (q01 == q02) {
		DBG("WOOF");
		// minmax didnt change => ai2 between ai0 and ai1
		if (a0 < a1) a2 = a1 - q12;
		else a2 = a1 + q12;
	} else {
		DBG("MIAUW");
		if (a0 < a1) {
			if (q12 >= q02) a2 = a1 - q12;
			else a2 = a1 + q12;
		} else {
			if (q12 == q02) a2 = a1 + q12;
			else if (q12 < q02) a2 = a1 - q12;
			else a2 = a1 + q12;
		}
	}

	return a2;
}

void solve(int N) {
	qcache.clear();
	qcache.resize(N+1, vi(N+1, -1));
	queries = 0;

	vi ans(N+1);
	ans[2] = q(1, 2);

	for (int i = 1; i+2 <= N; ++i) {
		int i0=i;
		int i1=i+1;
		int i2=i+2;

		int q02 = q(i0, i2);
		int q12 = q(i1, i2);

		ans[i2] = get_next(ans[i0], ans[i1], q02, q12);
	}

	DBG(queries);

	auto [mi, ma] = minmax_element(ans.begin()+1, ans.end());

	if (mi < ma) {
		DBG("good first guess");
		int offset = N - *ma;
		for (int i = 1; i <= N; ++i) {
			DBG(offset + ans[i]);
			answer(i, ans[i] + offset);
		}
	} else {
		DBG("bad first guess");
		int offset = *ma + 1;
		for (int i = 1; i <= N; ++i) {
			DBG(offset - ans[i]);
			answer(i, offset - ans[i]);
		}
	}
}

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