Submission #125365

#	Time	Username	Problem	Language	Result	Execution time	Memory
125365		teomrn	Mechanical Doll (IOI18_doll)	C++14	53 / 100	174 ms	20820 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 nod = X.size() + 1;
		X.push_back(0);
		Y.push_back(0);
		int st = build_switch(h - 1, from, fii);
		int dr = build_switch(h - 1, from + (1 << (h - 1)), fii);
		X[nod - 1] = st;
		Y[nod - 1] = dr;
		return -nod;
	}
	return fii[from];
}

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

	urm[0].push_back(A[0]);
	A.push_back(0);
	for (int i = 0; i + 1 < A.size(); i++)
		urm[A[i]].push_back(A[i + 1]);

	C.resize(m + 1);

	for (int i = 0; i <= m; i++) {
		if (urm[i].empty())
			continue;
		int nr = urm[i].size();
		int h = 0, root = -(X.size() + 1);
		while ((1 << h) < nr)
			h++;
		auto ord = build_ord(h);
		// o sa am ordinea ord cand apelez cv de adancime h

		int decalaj = ord.size() - nr;
		for (auto & j : ord) {
			if (j < decalaj)
				j = root;
			else {
				assert(j - decalaj < urm[i].size());
				j = urm[i][j - decalaj];
			}
		}

		C[i] = build_switch(h, 0, ord);
	}

	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i + 1 < A.size(); i++)
      |                  ~~~~~~^~~~~~~~~~
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:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     assert(j - decalaj < urm[i].size());
      |            ~~~~~~~~~~~~^~~~~~~~~~~~~~~

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