Submission #207852

#	Time	Username	Problem	Language	Result	Execution time	Memory
207852		atoiz	Minerals (JOI19_minerals)	C++14	100 / 100	50 ms	4212 KiB

minerals

#include "minerals.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>

#define NDEBUG

using namespace std;

namespace Solver {
	const int INF = 1e9;
	int curCnt;
	vector<int> bestSplit, cost;
	vector<bool> inside;

	bool ask(int x) // -> return if paired is inside
	{
		inside[x] = !inside[x];
		int diff = Query(x) - curCnt;
		curCnt += diff;
		// cerr << "ask " << x << ": " << (diff != 0) << ' ' << curCnt << ' ' << inside[x] << endl;
		return diff == 0;
	}

	void solve(vector<int> lef, vector<int> rig)
	{
		// cerr << "sol [ ";
		// for (int x : lef) cerr << x << ' ';
		// cerr << "] [ ";
		// for (int x : rig) cerr << x << ' ';
		// cerr << "]" << endl;

		// last of "rig" is always different from the rest of "rig"
		int N = (int) lef.size();
		if (N == 0) return;
		if (N == 1) return Answer(lef[0], rig[0]);
		if (N == 2) {
			assert(inside[rig[0]] != inside[rig[1]]);
			if (ask(lef[0]) != inside[rig[0]]) swap(lef[0], lef[1]);
			return Answer(lef[0], rig[0]), Answer(lef[1], rig[1]);
		}
		if (N == 3) {
			if (ask(lef[0]) == inside[rig.back()]) {
				Answer(lef[0], rig.back());
				lef.erase(lef.begin());
				rig.erase(prev(rig.end()));
				ask(rig.back());
				return solve(lef, rig);
			}
			if (ask(lef[1]) == inside[rig.back()]) {
				Answer(lef[1], rig.back());
				lef.erase(lef.begin() + 1);
				rig.erase(prev(rig.end()));
				swap(lef[0], lef[1]);
				return solve(rig, lef);
			}

			Answer(lef.back(), rig.back());
			lef.erase(prev(lef.end()));
			rig.erase(prev(rig.end()));
			ask(rig.back());
			return solve(lef, rig);
		}

		int split = bestSplit[N];
		for (int i = N - split; i < N - 1; ++i) ask(rig[i]);
		vector<int> lef1, lef2;
		lef1.reserve(N - split), lef2.reserve(split);
		for (int i = 0; i < N - 1; ++i) {
			if (ask(lef[i]) == inside[rig[0]]) lef1.push_back(lef[i]);
			else lef2.push_back(lef[i]);
		}

		if ((int) lef1.size() < N - split) {
			lef1.push_back(lef.back());
			ask(lef2.back());
		} else {
			lef2.push_back(lef.back());
			ask(lef1.back());
		}
		vector<int> rig1(rig.begin(), rig.end() - split), rig2(rig.end() - split, rig.end());

		solve(rig1, lef1);
		solve(rig2, lef2);
	}

	void run(int N)
	{
		curCnt = 0;
		cost.assign(N + 1, INF);
		bestSplit.resize(N + 1);
		inside.assign(N * 2 + 1, false);

		cost[0] = 0, cost[1] = 0, cost[2] = 1, cost[3] = 3, bestSplit[3] = 1;
		for (int i = 4; i <= N; ++i) {
			for (int &x = (bestSplit[i] = bestSplit[i - 1]); x + 1 < i && i + x + cost[x] + cost[i - x] > i + x + 1 + cost[x + 1] + cost[i - x - 1]; ++x);
			cost[i] = i + bestSplit[i] + cost[bestSplit[i]] + cost[i - bestSplit[i]] - 1;
		}
		// cerr << cost[N] + 2 * N << endl;

		vector<int> lef, rig;
		for (int i = 1; i < 2 * N; ++i) {
			if (ask(i)) lef.push_back(i);
			else rig.push_back(i);
		}
		if (lef.size() < rig.size()) lef.swap(rig);
		rig.push_back(2 * N);
		solve(lef, rig);
	}
}

void Solve(int N) 
{ Solver::run(N); }

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10