oj.uz

Submission #96692

# Submission time Handle Problem Language Result Execution time Memory
96692 2019-02-11T03:12:38 Z diamond_duke Mechanical Doll (IOI18_doll) C++11
100 / 100
 154 ms 10716 KB 
#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

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 37 ms 4740 KB Output is correct
3 Correct 37 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 53 ms 6172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 37 ms 4740 KB Output is correct
3 Correct 37 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 53 ms 6172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 90 ms 8468 KB Output is correct
9 Correct 102 ms 8620 KB Output is correct
10 Correct 154 ms 10716 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 37 ms 4740 KB Output is correct
3 Correct 37 ms 4936 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 53 ms 6172 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 90 ms 8468 KB Output is correct
9 Correct 102 ms 8620 KB Output is correct
10 Correct 154 ms 10716 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 90 ms 10388 KB Output is correct
15 Correct 62 ms 7788 KB Output is correct
16 Correct 87 ms 10156 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 99 ms 10524 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 6920 KB Output is correct
3 Correct 59 ms 7404 KB Output is correct
4 Correct 79 ms 9628 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 52 ms 6920 KB Output is correct
3 Correct 59 ms 7404 KB Output is correct
4 Correct 79 ms 9628 KB Output is correct
5 Correct 90 ms 10036 KB Output is correct
6 Correct 85 ms 9884 KB Output is correct
7 Correct 118 ms 9908 KB Output is correct
8 Correct 84 ms 9652 KB Output is correct
9 Correct 54 ms 7412 KB Output is correct
10 Correct 86 ms 9628 KB Output is correct
11 Correct 93 ms 9544 KB Output is correct
12 Correct 59 ms 7496 KB Output is correct
13 Correct 55 ms 7480 KB Output is correct
14 Correct 59 ms 7620 KB Output is correct
15 Correct 59 ms 7748 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 59 ms 7156 KB Output is correct
18 Correct 53 ms 7132 KB Output is correct
19 Correct 87 ms 7480 KB Output is correct
20 Correct 87 ms 9628 KB Output is correct
21 Correct 84 ms 9524 KB Output is correct
22 Correct 85 ms 9532 KB Output is correct