Submission #125394

#	Time	Username	Problem	Language	Result	Execution time	Memory
125394		teomrn	Mechanical Doll (IOI18_doll)	C++14	100 / 100	146 ms	15312 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 normalize(int * v, int l)
{
	vector <int> nrm;
	for (int i = 0; i < l; i++)
		nrm.push_back(v[i]);
	sort(nrm.begin(), nrm.end());
	for (int i = 0; i < l; i++)
		v[i] = lower_bound(nrm.begin(), nrm.end(), v[i]) - nrm.begin();
}

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;

	normalize(ord.data() + dec, ord.size() - dec);
	for (int i = 0; i < dec; i++)
		ord[i] = -1e9;
	for (auto & i : ord) {
		if (i >= 0) {
			assert(i + 1 < A.size());
			i = A[i + 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;

	//cerr << "Am folosit " << X.size() << " chestii\n";
	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:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    assert(i + 1 < A.size());
      |           ~~~~~~^~~~~~~~~~

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