Submission #361700

#	Time	Username	Problem	Language	Result	Execution time	Memory
361700		NachoLibre	Mechanical Doll (IOI18_doll)	C++17	100 / 100	135 ms	12928 KiB

doll

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
#ifndef wambule
#include "doll.h"
#else
void answer(vint c, vint x, vint y) {
}
#endif

int n, o, w;
vint a, x, y, c, cp;

int N() {
	++w;
	x.push_back(0);
	y.push_back(0);
	return w;
}

void C(int l, int r, int d, int x) {
	if(l == r) {
		c[l] = x;
		return;
	}
	int m = (l + r) / 2;
	C(l, m, d + 1, x);
	C(m + 1, r, d + 1, x + (1 << d));
}

void B(int l, int r, int z) {
	int m = (l + r) / 2;
	if(m < o - n + 1) {
		x[z - 1] = -1;
	} else if(l == m) {
		x[z - 1] = a[cp[l]];
	} else {
		x[z - 1] = -N();
		B(l, m, w);
	}
	if(r == m + 1) {
		y[z - 1] = a[cp[r]];
	} else {
		y[z - 1] = -N();
		B(m + 1, r, w);
	}
}

void create_circuit(int m, vint _a) {
	//  //  //  //  //  //  //  //
	a = _a;
	a.push_back(0);
	n = a.size();
	o = (1 << ((int)log2(n - 1) + 1));
	//  //  //  //  //  //  //  //
	c.resize(o + 1);
	C(1, o, 0, 0);
	vector<pair<int, int>> v;
	for(int i = o - n + 1; i <= o; ++i) {
		v.push_back({c[i], i});
	}
	sort(v.begin(), v.end()); cp = c;
	for(int i = 0; i < v.size(); ++i) {
		cp[v[i].second] = i;
	}
	//  //  //  //  //  //  //  //
	B(1, o, N());
	//  //  //  //  //  //  //  //
	answer(vector<int>(m + 1, -1), x, y);
	//  //  //  //  //  //  //  //
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vint)':
doll.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 0; i < v.size(); ++i) {
      |                 ~~^~~~~~~~~~

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