Submission #125388

#	Time	Username	Problem	Language	Result	Execution time	Memory
125388		teomrn	Mechanical Doll (IOI18_doll)	C++14	47 / 100	129 ms	15320 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 200010;
vector <int> X, Y, C;
int n, m;
vector <int> urm[NMAX], act;


vector <int> build_ord(int h)
{
	if (h == 0)
		return { 0 };
	auto x = build_ord(h - 1);
	auto y = x;
	for (auto & i : x)
		i *= 2;
	for (auto & i : y)
		i = 2 * i + 1;
	for (auto i : y)
		x.push_back(i);
	return x;
}

int build_switch(int h, int from, vector <int> & fii)
{
	if (h != 0) {
		int st = build_switch(h - 1, from, fii);
		int dr = build_switch(h - 1, from + (1 << (h - 1)), fii);
		if (st == -1e9 && dr == -1e9)
			return -1e9;
		int nod = X.size() + 1;
		X.push_back(st);
		Y.push_back(dr);
		return -nod;
	}
	return fii[from];
}

void create_circuit(int M, std::vector<int> A) {
	n = A.size(), m = M;

	A.push_back(0);

	C.resize(m + 1);
	C[0] = A[0];

	int h = 0;
	while ((1 << h) < n)
		h++;
	auto ord = build_ord(h);
	int dec = ord.size() - n;

	for (auto & i : ord) {
		if (i < dec)
			i = -1e9;
		else {
			assert(i - dec + 1 < A.size());
			i = A[i - dec + 1];
		}
	}

	int root = build_switch(h, 0, ord);
	fill(C.begin() + 1, C.end(), root);

	for (auto & i : X)
		if (i == -1e9)
			i = root;
	for (auto & j : Y)
		if (j == -1e9)
			j = root;

	answer(C, X, Y);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from doll.cpp:2:
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    assert(i - dec + 1 < A.size());
      |           ~~~~~~~~~~~~^~~~~~~~~~

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