Submission #779494

#	Time	Username	Problem	Language	Result	Execution time	Memory
779494		sadsa	Xylophone (JOI18_xylophone)	C++17	0 / 100	6 ms	348 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 q(int l, int r) {
	if (l > r) swap(l, r);

	int Q;

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

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

	return Q;
}

int find_one(int N) {
	DBG("find_one=====================");
	int l = 1;
	int r = N;

	int target = N-1;

	while (l != r) {
		DBG("l,r", l, r);
		if (r-l == 1) {
			if (q(l, N) == target) {
				r = l;
			} else {
				l = r;
			}
			break;
		}

		int mid = (l + r) / 2;
		DBG("mid", mid);

		if (q(mid, N) == target) {
			l = mid;
		} else {
			r = mid-1;
		}
	}
	return l;
}

int find_N(int index1, int N) {
	DBG("find_N===============");
	int l = index1+1;
	int r = N;

	int target = N-1;

	while (l != r) {
		DBG("l,r", l, r);
		int mid = (l + r) / 2;
		DBG("mid", mid);

		if (q(index1, mid) == target) {
			r = mid;
		} else {
			l = mid+1;
		}
	}
	return l;
}

// 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));

	int index1 = find_one(N);
	DBG("index 1:", index1);
	int indexN = find_N(index1, N);
	DBG("index N:", indexN);

	vi ans(N+1);
	ans[index1] = 1;
	ans[indexN] = N;

	ans[index1+1] = 1+q(index1, index1+1);

	for (int i = index1; i+2 <= N; ++i) {
		DBG("starti", 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("next guess", ans[i0], ans[i1], ans[i2]);
		DBG("with info", q02, q12);
	}

	for (int i = index1+1; i-2 > 0; --i) {
		int i0 = i;
		int i1 = i-1;
		int i2 = i-2;

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

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

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

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