Submission #228039

#	Time	Username	Problem	Language	Result	Execution time	Memory
228039		staniewzki	Mechanical Doll (IOI18_doll)	C++17	37 / 100	190 ms	12184 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;
	while((1 << dep) < size(A))
		dep++;
	A.back() = -1;
	while(size(A) < (1 << dep))
		A.emplace_back(-1);
	A.back() = 0;

	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;
		int q = min<int>(1 << (d - 1), size(t));

		vector<int> l, r;
		for(int i = 0; i < size(t); i++) {
			if(i % 2 == 1 && size(r) < size(t) - q) 
				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, A);
	answer(vector<int>(M + 1, -1), x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:9:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  while((1 << dep) < size(A))
      |        ~~~~~~~~~~~^~~~~~~~~
doll.cpp:12:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |  while(size(A) < (1 << dep))
      |        ~~~~~~~~^~~~~~~~~~~~
doll.cpp: In lambda function:
doll.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   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:38:29:   required from here
doll.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

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