oj.uz

Submission #228041

# Submission time Handle Problem Language Result Execution time Memory
228041 2020-04-29T16:23:04 Z staniewzki Mechanical Doll (IOI18_doll) C++17
100 / 100
 185 ms 11620 KB 
#include<bits/stdc++.h>
using namespace std;
 
#include "doll.h"

void create_circuit(int M, vector<int> A) {
	A.emplace_back(0);
	int dep = 0;
	vector<int> r = {1};
	while((1 << dep) < size(A)) {
		for(int i = 0; i < (1 << dep); i++) {
			r[i] = r[i] * 2 - 1;
			r.emplace_back(r[i] + 1);
		}
		dep++;
	}

	int q = 1 << dep, z = q - size(A), u = 0;
	vector<int> f(q);
	for(int i = 0; i < q; i++)
		f[i] = (r[i] <= z ? -1 : A[u++]);

	vector<int> x, y;
	auto construct = [&](auto self, int d, vector<int> t)  {
		if(*max_element(t.begin(), t.end()) == -1) return -1;
		if(d == 0) return t[0];

		x.emplace_back(), y.emplace_back();
		int v = size(x) - 1;

		vector<int> l, r;
		for(int i = 0; i < size(t); i++) {
			if(i % 2 == 1)
				r.emplace_back(t[i]);
			else
				l.emplace_back(t[i]);
		}

		x[v] = self(self, d - 1, l);
		y[v] = self(self, d - 1, r);
		return -(v + 1);
	};

	construct(construct, dep, f);
	answer(vector<int>(M + 1, -1), x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  while((1 << dep) < size(A)) {
      |        ~~~~~~~~~~~^~~~~~~~~
doll.cpp: In lambda function:
doll.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0; i < size(t); i++) {
      |                  ~~^~~~~~~~~
doll.cpp: In instantiation of 'create_circuit(int, std::vector<int>)::<lambda(auto:23, int, std::vector<int>)> [with auto:23 = create_circuit(int, std::vector<int>)::<lambda(auto:23, int, std::vector<int>)>]':
doll.cpp:44:29:   required from here
doll.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 58 ms 5056 KB Output is correct
3 Correct 67 ms 5116 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 78 ms 5852 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 58 ms 5056 KB Output is correct
3 Correct 67 ms 5116 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 78 ms 5852 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 9812 KB Output is correct
9 Correct 103 ms 9896 KB Output is correct
10 Correct 142 ms 11444 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 2 ms 204 KB Output is correct
2 Correct 58 ms 5056 KB Output is correct
3 Correct 67 ms 5116 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 972 KB Output is correct
6 Correct 78 ms 5852 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 98 ms 9812 KB Output is correct
9 Correct 103 ms 9896 KB Output is correct
10 Correct 142 ms 11444 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 151 ms 10992 KB Output is correct
15 Correct 110 ms 9792 KB Output is correct
16 Correct 159 ms 11508 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 139 ms 10920 KB Output is correct
21 Correct 2 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 204 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 86 ms 9824 KB Output is correct
3 Correct 87 ms 9804 KB Output is correct
4 Correct 132 ms 11556 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 86 ms 9824 KB Output is correct
3 Correct 87 ms 9804 KB Output is correct
4 Correct 132 ms 11556 KB Output is correct
5 Correct 148 ms 11524 KB Output is correct
6 Correct 135 ms 10900 KB Output is correct
7 Correct 154 ms 11572 KB Output is correct
8 Correct 185 ms 11316 KB Output is correct
9 Correct 93 ms 9792 KB Output is correct
10 Correct 150 ms 11448 KB Output is correct
11 Correct 142 ms 11552 KB Output is correct
12 Correct 111 ms 9796 KB Output is correct
13 Correct 91 ms 9892 KB Output is correct
14 Correct 93 ms 9844 KB Output is correct
15 Correct 93 ms 9896 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 90 ms 7160 KB Output is correct
18 Correct 109 ms 9812 KB Output is correct
19 Correct 90 ms 9792 KB Output is correct
20 Correct 133 ms 10872 KB Output is correct
21 Correct 147 ms 11576 KB Output is correct
22 Correct 134 ms 11620 KB Output is correct