Submission #228041

#	Time	Username	Problem	Language	Result	Execution time	Memory
228041		staniewzki	Mechanical Doll (IOI18_doll)	C++17	100 / 100	185 ms	11620 KiB

doll

#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 (stderr)

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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56