Submission #778862

#	Time	Username	Problem	Language	Result	Execution time	Memory
778862		sadsa	Xylophone (JOI18_xylophone)	C++17	0 / 100	0 ms	208 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);
	if (l == r) return 0;
	if (qcache[l][r] != -1) return qcache[l][r];
	return qcache[l][r] = query(l, r);
}

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

	int target = N-1;

	while (l != r) {
		//DBG(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;
}

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

	int one_index = find_one(N);

	for (int i = 1; i <= N; ++i) {
		answer(i, 1+q(one_index, i));
	}
}

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