Submission #779534

#	Time	Username	Problem	Language	Result	Execution time	Memory
779534		sadsa	Xylophone (JOI18_xylophone)	C++17	47 / 100	268 ms	98612 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;
}

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

	int target = N-1;

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

		if (q(mid, N) == target) {
			l = mid;
		} else {
			r = 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));
	queries = 0;

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

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

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

	bitset<5001> found;
	found[1] = 1;
	found[ans[index1+1]] = 1;

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

	for (int i = index1+1; i-2 > 0 && found.count() < N-1; --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);
		found[ans[i2]] = 1;
	}

	if (found.count() == N-1) {
		int missing_a;
		for (int i = 1; i <= N; ++i) {
			if (!found[i]) {
				missing_a = i;
				break;
			}
		}
		*find(ans.begin()+1, ans.end(), 0) = missing_a;
	}

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

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:110:49: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  for (int i = index1; i+2 <= N && found.count() < N-1; ++i) {
      |                                   ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:125:50: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |  for (int i = index1+1; i-2 > 0 && found.count() < N-1; --i) {
      |                                    ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |  if (found.count() == N-1) {
      |      ~~~~~~~~~~~~~~^~~~~~
xylophone.cpp:145:38: warning: 'missing_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |   *find(ans.begin()+1, ans.end(), 0) = missing_a;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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