Submission #96692

#	Time	Username	Problem	Language	Result	Execution time	Memory
96692		diamond_duke	Mechanical Doll (IOI18_doll)	C++11	100 / 100	154 ms	10716 KiB

doll

#include "doll.h"
#include <functional>
std::vector<int> get_rev(int n)
{
	std::vector<int> rev(n);
	rev[n - 1] = n - 1;
	for (int i = 1, j = n >> 1; i + 1 < n; i++)
	{
		rev[i] = j;
		int k = n >> 1;
		while (j & k)
		{
			j ^= k;
			k >>= 1;
		}
		j |= k;
	}
	return rev;
}
void create_circuit(int m, std::vector<int> arr)
{
	int n = arr.size(), len = 1;
	arr.push_back(0);
	while (len < n)
		len <<= 1;
	auto rev = get_rev(len);
	std::vector<int> seq(len, -1), idx(len), X, Y;
	for (int i = len - n; i < len; i++)
		seq[rev[i]] = i;
	for (int i = 0, j = 0; i < len; i++)
	{
		if (~seq[i])
			idx[seq[i]] = ++j;
	}
	std::function<int (int, int)> solve = [&] (int l, int r) -> int
	{
		if (l == r)
			return l >= len - n ? arr[idx[l]] : m + 1;
		int mid = l + r >> 1;
		int lson = solve(l, mid), rson = solve(mid + 1, r);
		if (lson == m + 1 && rson == m + 1)
			return m + 1;
		X.push_back(lson);
		Y.push_back(rson);
		return -X.size();
	};
	int rt = solve(0, len - 1);
	std::vector<int> C(m + 1, rt);
	C[0] = arr[0];
	auto trans = [&] (std::vector<int> &vec)
	{
		for (auto &i : vec)
		{
			if (i == m + 1)
				i = rt;
		}
	};
	trans(X);
	trans(Y);
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In lambda function:
doll.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56