Submission #112235

#	Time	Username	Problem	Language	Result	Execution time	Memory
112235		AngusRitossa	Minerals (JOI19_minerals)	C++14	100 / 100	73 ms	3068 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#include <chrono>
#include <random>

#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, pre;
vector<int> before, after;
int other[2*70000];
int c;
int doQuery(int a)
{
	c++;
	assert(c != 1.1e6);
	D("querying %d\n", a);
	return Query(a);
}
void solve(vector<int> &b, vector<int> &a, bool inv = 0, bool shouldrem = 1, int half = -1)
{
	D("\n%lu %lu inv %d\n", a.size(), b.size(), inv);
	for (auto i : b) D("%d ", i);
	D(" a\n");
	for (auto i : a) D("%d ", i);
	D(" b\n");
	assert(a.size() == b.size());
	if (b.size() == 1)
	{
		other[a[0]] = b[0];
		return;
	}
	vector<int> firsthalf, secondhalf;
	vector<int> fa, sa;
	int ignore = 1e9;
	if (half < 0) ignore = ((int)b.size()) + half+1;
	if (half < 0)
	{
		half = b.size()/2;
		if (shouldrem) half += b.size()/10;
	}
	for (int i = 0; i < b.size(); i++)
	{
		if (i < half) 
		{
			firsthalf.push_back(b[i]);
			if (i >= ignore) pre = doQuery(b[i]);
		}
		else 
		{
			secondhalf.push_back(b[i]);
			if (shouldrem && i < ignore) pre = doQuery(b[i]);
			else if (shouldrem) D("ignored %d\n", b[i]);
		}
	}
	if (inv) swap(firsthalf, secondhalf);
	int oldpre = pre;
	int sta = 0;
	shuffle(a.begin(), a.end(), rng);
	for (auto i : a)
	{
		if (fa.size() == b.size()-1) { sa.push_back(i); continue; }
		if (sa.size() == b.size()-1) { fa.push_back(i); continue; }
		if (fa.size() == firsthalf.size() && pre < oldpre)
		{
			sa.insert(sa.begin(), i); sta++;
			continue;
		}
		else if (sa.size() == secondhalf.size())
		{
			sta--;
			fa.push_back(i);
		//	D("doing this! %d\n", i);
			continue;
		}
		int q = doQuery(i);
		if (q == pre)
		{
			fa.push_back(i);
		}
		else
		{
			sa.push_back(i);
		}
		pre = q;
	}
	int h = -1;
	if (sta < 0) h = sta-1;
	if (h == -1) solve(firsthalf, fa, 0, 1, h);
	else solve(fa, firsthalf, pre < oldpre, 1, h);
	if (pre >= oldpre) 
	{ 
		solve(sa, secondhalf, 0);
	}
	else
	{
		sta = max(sta, 0);
		int half = sa.size()/2;
		half -= sa.size()/10;
		if (sta-1 >= half) half += sa.size()/10;
		while (sta-1 >= half)
		{
			pre = doQuery(sa[--sta]);
		}
		for (int i = sta; i < half; i++) pre = doQuery(sa[i]);
		solve(sa, secondhalf, 0, 0, half);
	}
}
void Solve(int N) 
{
	n = N;
	for (int i = 1; i <= 2*n; i++)
	{
		int q = doQuery(i);
		if (q != pre) before.push_back(i);
		else after.push_back(i);
		pre = q;
	}
	solve(before, after);
	for (int i = 1; i <= 2*n; i++)
	{
		if (other[i]) 
		{
			Answer(i, other[i]);
		}
	}
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&, bool, bool, int)':
minerals.cpp:27:12: warning: unused variable 'i' [-Wunused-variable]
  for (auto i : b) D("%d ", i);
            ^
minerals.cpp:29:12: warning: unused variable 'i' [-Wunused-variable]
  for (auto i : a) D("%d ", i);
            ^
minerals.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~

• 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