제출 #778708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
778708		Boas	Xylophone (JOI18_xylophone)	C++17	100 / 100	75 ms	688 KiB

xylophone

#include "xylophone.h"
using namespace std;
#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <unordered_map>
//#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#include <chrono>
using namespace chrono;


struct pairhash
{
public:
	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, int, pairhash> queries;

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

void solve(int N)
{
	int a = 1, b = N;
	while (a < b)
	{
		int k = (a + b) / 2;
		int value = ownQuery(1, k);
		if (value == N - 1) b = k;
		else a = k + 1;
	}
	int maxIndex = a == b ? a : -1;
	a = 1, b = maxIndex - 1;
	while (a < b)
	{
		int k = (a + b + 1) / 2;
		int value = ownQuery(k, maxIndex);
		if (value == N - 1) a = k;
		else b = k - 1;
	}
	int oneIndex = a == b ? a : -1;
	bitset<5001> found;
	vector<int> values(N + 1, -1);
	found[0] = true;
	for (int i = N + 1; i < 5001; i++)
	{
		found[i] = true;
	}
	found[1] = true;
	found[N] = true;
	values[oneIndex] = 1;
	values[maxIndex] = N;
	bool cantProgress = true;
	while (!found.all())
	{
		cantProgress = true;
		for (int i = 1; i <= N; i++)
		{
			if (values[i] != -1)
			{
				int j = i - 1;
				if (j > 0 && values[j] == -1)
				{
					int v = ownQuery(j, i);
					int opt1 = values[i] + v;
					int opt2 = values[i] - v;
					if (opt1 <= 1)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 <= 1)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (opt1 >= N)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 >= N)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (found[opt1])
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (found[opt2])
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
				}
				j = i + 1;
				if (j < N && values[j] == -1)
				{
					int v = ownQuery(i, j);
					int opt1 = values[i] + v;
					int opt2 = values[i] - v;
					if (opt1 <= 1)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 <= 1)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (opt1 >= N)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 >= N)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (found[opt1])
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (found[opt2])
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
				}
			}
		}
		if (cantProgress) break;
	}
	while (!found.all())
	{
		cantProgress = true;
		for (int i = 1; i <= N; i++)
		{
			if (values[i] != -1)
			{
				int j = i - 1;
				if (j > 0 && values[j] == -1)
				{
					int v = ownQuery(j, i);
					int opt1 = values[i] + v;
					int opt2 = values[i] - v;
					if (opt1 <= 1)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 <= 1)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (opt1 >= N)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 >= N)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (found[opt1])
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (found[opt2])
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else
					{
						int v2 = query(j, j + 2);
						int ma = max(values[j + 2], values[i]);
						int mi = min(values[j + 2], values[i]);
						int v2Opt1 = max(opt1, ma) - min(opt1, mi);
						int v2Opt2 = max(opt2, ma) - min(opt2, mi);
						if (v2 == v2Opt1 && v2 != v2Opt2)
						{
							cantProgress = false;
							found[opt1] = true;
							values[j] = opt1;
						}
						else if (v2 == v2Opt2 && v2 != v2Opt1)
						{
							cantProgress = false;
							found[opt2] = true;
							values[j] = opt2;
						}
						else
						{
							cerr << "I didn't consider this to be possible. Please take a look!";
							throw;
						}
					}
				}
				j = i + 1;
				if (j <= N && values[j] == -1)
				{
					int v = ownQuery(i, j);
					int opt1 = values[i] + v;
					int opt2 = values[i] - v;
					if (opt1 <= 1)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 <= 1)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (opt1 >= N)
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (opt2 >= N)
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else if (found[opt1])
					{
						values[j] = opt2; cantProgress = false; found[opt2] = true;
					}
					else if (found[opt2])
					{
						values[j] = opt1; cantProgress = false; found[opt1] = true;
					}
					else
					{
						int v2 = ownQuery(j - 2, j);
						int ma = max(values[j - 2], values[i]);
						int mi = min(values[j - 2], values[i]);
						int v2Opt1 = max(opt1, ma) - min(opt1, mi);
						int v2Opt2 = max(opt2, ma) - min(opt2, mi);
						if (v2 == v2Opt1 && v2 != v2Opt2)
						{
							cantProgress = false;
							found[opt1] = true;
							values[j] = opt1;
						}
						else if (v2 == v2Opt2 && v2 != v2Opt1)
						{
							cantProgress = false;
							found[opt2] = true;
							values[j] = opt2;
						}
						else
						{
							cerr << "I didn't consider this to be possible. Please take a look!";
							throw;
						}
					}
				}
			}
		}
		if (cantProgress)
		{
			cerr << "I didn't consider this to be possible. Please take a look!";
			throw;
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (values[i] == -1) throw;
		answer(i, values[i]);
	}

}

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