oj.uz

Submission #777252

# Submission time Handle Problem Language Result Execution time Memory
777252 2023-07-08T21:39:20 Z Boas Xylophone (JOI18_xylophone) C++17
0 / 100
 2000 ms 208 KB 
#include "xylophone.h"

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

struct pairhash
{
public:
	template <typename T, typename U>
	std::size_t operator()(const std::pair<T, U>& x) const
	{
		return std::hash<T>()(x.first) ^ std::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) / 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;
					else if (opt2 <= 1) { values[j] = opt1; cantProgress = false; }
					else if (opt1 >= N) { values[j] = opt2; cantProgress = false; }
					else if (opt2 >= N) { values[j] = opt1; cantProgress = false; }
					else if (found[opt1]) { values[j] = opt2; cantProgress = false; }
					else if (found[opt2]) { values[j] = opt1; cantProgress = false; }
				}
				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;
					else if (opt2 <= 1) { values[j] = opt1; cantProgress = false; }
					else if (opt1 >= N) { values[j] = opt2; cantProgress = false; }
					else if (opt2 >= N) { values[j] = opt1; cantProgress = false; }
					else if (found[opt1]) { values[j] = opt2; cantProgress = false; }
					else if (found[opt2]) { values[j] = opt1; cantProgress = false; }
				}
			}
		}
		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;
					else if (opt2 <= 1) { values[j] = opt1; cantProgress = false; }
					else if (opt1 >= N) { values[j] = opt2; cantProgress = false; }
					else if (opt2 >= N) { values[j] = opt1; cantProgress = false; }
					else if (found[opt1]) { values[j] = opt2; cantProgress = false; }
					else if (found[opt2]) { values[j] = opt1; cantProgress = false; }
					else
					{
						int v2 = query(j, j + 2);
						int ma = max(values[j], values[i]);
						int mi = min(values[j], values[i]);
						int v2Opt1 = max(opt1, ma) - min(opt1, mi);
						int v2Opt2 = max(opt2, ma) - min(opt2, mi);
						if (v2 == v2Opt1 && v2 != v2Opt2) values[j] = opt1;
						else if (v2 == v2Opt2 && v2 != v2Opt1) values[j] = opt2;
						else
							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;
					else if (opt2 <= 1) { values[j] = opt1; cantProgress = false; }
					else if (opt1 >= N) { values[j] = opt2; cantProgress = false; }
					else if (opt2 >= N) { values[j] = opt1; cantProgress = false; }
					else if (found[opt1]) { values[j] = opt2; cantProgress = false; }
					else if (found[opt2]) { values[j] = opt1; cantProgress = false; }
					else
					{
						int v2 = ownQuery(j - 2, j);
						int ma = max(values[j], values[i]);
						int mi = min(values[j], values[i]);
						int v2Opt1 = max(opt1, ma) - min(opt1, mi);
						int v2Opt2 = max(opt2, ma) - min(opt2, mi);
						if (v2 == v2Opt1 && v2 != v2Opt2) values[j] = opt1;
						else if (v2 == v2Opt2 && v2 != v2Opt1) values[j] = opt2;
						else
						{
							throw;
						}
					}
				}
			}
		}
		if (cantProgress) break;
	}
	for (int i = 1; i <= N; i++)
	{
		answer(i, values[i]);
	}

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Execution timed out 3038 ms 208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Execution timed out 3038 ms 208 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Execution timed out 3038 ms 208 KB Time limit exceeded
4 Halted 0 ms 0 KB -