Submission #111527

#	Time	Username	Problem	Language	Result	Execution time	Memory
111527		diamond_duke	Koala Game (APIO17_koala)	C++11	100 / 100	89 ms	648 KiB

koala

#include "koala.h"
#include <algorithm>
#include <vector>
std::vector<bool> query(const std::vector<int> &vec)
{
	static int B[105], R[105];
	int n = vec.size();
	for (int i = 0; i < n; i++)
		B[i] = vec[i];
	playRound(B, R);
	std::vector<bool> res(n);
	for (int i = 0; i < n; i++)
		res[i] = R[i] > B[i];
	return res;
}
int minValue(int n, int m)
{
	std::vector<int> vec(n);
	vec[0] = 1;
	auto res = query(vec);
	for (int i = 0; i < n; i++)
	{
		if (!res[i])
			return i;
	}
	return -1;
}
int maxValue(int n, int m)
{
	std::vector<bool> in(n, true);
	int cnt = n;
	while (cnt > 1)
	{
		int w = m / cnt;
		std::vector<int> vec(n);
		for (int i = 0; i < n; i++)
			vec[i] = in[i] ? w : 0;
		auto res = query(vec);
		cnt = 0;
		for (int i = 0; i < n; i++)
		{
			in[i] = in[i] & res[i];
			cnt += in[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (in[i])
			return i;
	}
	return -1;
}
int greaterValue(int n, int m)
{
	std::vector<int> vec(n);
	vec[0] = vec[1] = 4;
	auto res = query(vec);
	if (res[0] != res[1])
		return res[1];
	if (res[0])
	{
		vec[0] = vec[1] = 8;
		return query(vec)[1];
	}
	vec[0] = vec[1] = 2;
	res = query(vec);
	if (res[0] != res[1])
		return res[1];
	vec[0] = vec[1] = 1;
	return query(vec)[1];
}
int idx[105], val[105], n;
inline int calc_sum(int l, int r) { return (l + r) * (r - l + 1) / 2; }
int get_val(int l, int r)
{
	int mn = 1, mx = n / (r - l + 1);
	while (mn <= mx)
	{
		int mid = mn + mx >> 1, rem = 0, cur = r, left = 0;
		for (int i = 0; i < n; i++)
		{
			if (i < l || i > r)
				val[i] = 1;
			else
			{
				val[i] = 0;
				rem++;
			}
		}
		while (rem > mid)
		{
			val[cur--] = mid + 1;
			rem -= mid + 1;
		}
		val[cur] = rem;
		while (true)
		{
			int goal = mid + 1 - val[cur];
			if (left + goal > l || calc_sum(left + 1, left + goal) >= cur)
				break;
			for (int i = left; i < left + goal; i++)
			{
				val[i]--;
				val[cur]++;
			}
			left += goal;
			if (--cur < l)
				break;
		}
		if (val[l] > mid)
			mn = mid + 1;
		else if (val[r] <= mid)
			mx = mid - 1;
		else
			return mid;
	}
	throw;
}
void solve(int l, int r, const std::vector<int> &vec)
{
	if (l == r)
	{
		idx[l] = vec[0];
		return;
	}
	int w = get_val(l, r);
	std::vector<int> qry(n);
	for (int i = 0; i < n; i++)
		qry[i] = std::binary_search(vec.begin(), vec.end(), i) ? w : 0;
	auto res = query(qry);
	std::vector<int> vec_l, vec_r;
	for (int u : vec)
		(res[u] ? vec_r : vec_l).push_back(u);
	solve(l, r - vec_r.size(), vec_l);
	solve(r - vec_r.size() + 1, r, vec_r);
}
void allValues(int _n, int m, int *arr)
{
	n = _n;
	std::vector<int> seq(n);
	for (int i = 0; i < n; i++)
		seq[i] = i;
	if (m == n)
	{
		solve(0, n - 1, seq);
		for (int i = 0; i < n; i++)
			arr[idx[i]] = i + 1;
		return;
	}
	std::stable_sort(seq.begin(), seq.end(), [&] (int x, int y)
	{
		std::vector<int> vec(n, 0);
		vec[x] = vec[y] = n;
		return (bool)query(vec)[y];
	});
	for (int i = 0; i < n; i++)
		arr[seq[i]] = i + 1;
}

Compilation message (stderr)

koala.cpp: In function 'int get_val(int, int)':
koala.cpp:79:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = mn + mx >> 1, rem = 0, cur = r, left = 0;
             ~~~^~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53