Submission #781148

#	Time	Username	Problem	Language	Result	Execution time	Memory
781148		Boas	Xylophone (JOI18_xylophone)	C++17	100 / 100	450 ms	660 KiB

xylophone

//#define _CRT_SECURE_NO_WARNINGS
//#include "grader.cpp"
#include "xylophone.h"
using namespace std;
#include <vector>
#include <bitset>
#include <unordered_map>
typedef vector<int16_t> vi;
typedef pair<int16_t, int16_t> pii;

struct pairhash
{
	template <typename T, typename U>
	size_t operator()(const pair<T, U>& x) const
	{
		return hash<T>()(x.first) * 100003 ^ hash<U>()(x.second);
	}
};

unordered_map<pii, int16_t, pairhash> queries;

int16_t ownQuery(int16_t a, int16_t b)
{
	if (queries.find({ a, b }) != queries.end())
	{
		return queries[{a, b}];
	}
	return queries[{a, b}] = query(a, b);
}

void queryAndProcess(const int16_t& i, const int16_t& d, bool& canProgress, const int16_t& N, bitset<5001>& notFound, vi& values, const bool& doExtra)
{
	if (i + d > N || i + d <= 0) return;
	if (values[i] == -1) return;
	if (values[i + d] != -1) return;
	int16_t v = d > 0 ? ownQuery(i, i + d) : ownQuery(i + d, i);
	int16_t opt1 = values[i] + v;
	int16_t opt2 = values[i] - v;
	int16_t result = 0; // 1 = opt1, 2 = opt2, 0 is unknown
	if (opt1 < 1) result = 2;
	else if (opt2 < 1) result = 1;
	else if (opt1 > N) result = 2;
	else if (opt2 > N) result = 1;
	else if (!notFound[opt1]) result = 2;
	else if (!notFound[opt2]) result = 1;
	if (result == 0)
	{
		if (!doExtra) return;
		int16_t v2 = d > 0 ? query(i - d, i + d) : query(i + d, i - d);
		int16_t ma = max(values[i - d], values[i]);
		int16_t mi = min(values[i - d], values[i]);
		int16_t v2Opt1 = max(opt1, ma) - min(opt1, mi);
		int16_t v2Opt2 = max(opt2, ma) - min(opt2, mi);
		result = v2 == v2Opt1 ? 1 : 2;
	}
	if (result == 1)
	{
		values[i + d] = opt1;
		notFound[opt1] = false;
	}
	else
	{
		values[i + d] = opt2;
		notFound[opt2] = false;
	}
	canProgress = true;
}

void solve(int N)
{
	int16_t a = 1, b = N;
	while (a < b)
	{
		int16_t k = (a + b) / 2;
		int16_t value = ownQuery(1, k);
		if (value == N - 1) b = k;
		else a = k + 1;
	}
	int16_t maxIndex = a;
	a = 1, b = maxIndex - 1;
	while (a < b)
	{
		int16_t k = (a + b + 1) / 2;
		int16_t value = ownQuery(k, maxIndex);
		if (value == N - 1) a = k;
		else b = k - 1;
	}
	int16_t oneIndex = a;
	bitset<5001> notFound;
	for (int16_t i = 2; i < N; i++) notFound[i] = true;
	vi values(N + 1, -1);
	values[oneIndex] = 1;
	values[maxIndex] = N;
	bool canProgress = true;
	while (canProgress)
	{
		canProgress = false;
		for (int16_t i = 1; i <= N; i++)
		{
			queryAndProcess(i, -1, canProgress, N, notFound, values, false);
			queryAndProcess(i, 1, canProgress, N, notFound, values, false);
			if (notFound.none()) break;
		}
	}
	canProgress = !notFound.none();
	while (canProgress)
	{
		canProgress = false;
		for (int16_t i = 1; i <= N; i++)
		{
			queryAndProcess(i, -1, canProgress, N, notFound, values, true);
			queryAndProcess(i, 1, canProgress, N, notFound, values, true);
			if (notFound.none()) break;
		}
	}
	for (int16_t i = 1; i <= N; i++)
	{
		if (values[i] == -1) throw;
		answer(i, values[i]);
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void queryAndProcess(const int16_t&, const int16_t&, bool&, const int16_t&, std::bitset<5001>&, vi&, const bool&)':
xylophone.cpp:53:11: warning: unused variable 'v2Opt2' [-Wunused-variable]
   53 |   int16_t v2Opt2 = max(opt2, ma) - min(opt2, mi);
      |           ^~~~~~

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