Submission #412062

#	Time	Username	Problem	Language	Result	Execution time	Memory
412062		Mlxa	Mechanical Doll (IOI18_doll)	C++14	100 / 100	312 ms	13124 KiB

doll

#include <bits/stdc++.h>
using namespace std;
#include "doll.h"
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second

const int MAX = 1e9;

vector<int> x, y, arr;
int solve(vector<int> idx) {
	assert(idx.size());
	if ((int)count(all(idx), -1) == (int)idx.size()) {
		return -1;
	}
	if (idx.size() == 1) {
		return idx[0];
	}
	x.push_back(0), y.push_back(0);
	int v = -(int)x.size();
	// cout << v << ": ";
	// for (int e : idx) {
	// 	cout << e << " ";
	// }
	// cout << endl;

	vector<int> lef, rig;
	for (int e : idx) {
		if (2 * lef.size() + 2 <= idx.size()) {
			lef.push_back(e);
		} else {
			rig.push_back(e);
		}
	}
	// cout << "div " << idx.size() << " " << lef.size() << " " << rig.size() << endl;
	// for (int i = 0; i < (int)idx.size(); ++i) {
	// 	(i % 2 ? rig : lef).push_back(idx[i]);
	// }
	assert(0 <= -1 - v && -1 - v < (int)x.size());
	assert(0 <= -1 - v && -1 - v < (int)y.size());
	int a = solve(lef), b = solve(rig);
	x[-1 - v] = a;
	y[-1 - v] = b;
	return v;
}

bool bit(int m, int i) {
	return (m >> i) & 1;
}

void create_circuit(int m, vector<int> a) {
	arr = a;
	int p = (int)a.size() + 1;
	while (p & (p - 1)) {
		++p;
	}
	vector<int> c(m + 1, -1), idx(p);
	iota(all(idx), 0);
	sort(all(idx), [&](int xx, int yy) {
		for (int i = 0; i < 20; ++i) {
			if (bit(xx ^ yy, i)) {
				return bit(yy, i);
			}
		}
		return false;
	});
	// for (int e : idx) {
	// 	cout << e << " ";
	// }
	// cout << endl;
	for (int i = 0; i < p - (int)a.size() - 1; ++i) {
		idx[i] = -1;
	}
	idx.back() = 0;
	vector<pair<int, int>> srt;
	for (int i = p - (int)a.size() - 1; i < p - 1; ++i) {
		srt.emplace_back(idx[i], i);
	}
	sort(all(srt));
	assert((int)srt.size() == (int)a.size());
	for (int i = 0; i < (int)srt.size(); ++i) {
		idx[srt[i].y] = a[i];
	}
	// for (int &e : idx) {
		// if (e < (int)a.size()) {
		// 	e = a[e];
		// } else if (e == p - 1) {
		// 	e = 0;
		// } else {
		// 	e = -1;
		// }
		// cout << e << " ";
	// }
	// cout << endl;
	int root = solve(idx);
	assert(root == -1);
	// cout << "===" << endl;
	// for (int e : x) {
	// 	cout << e << " ";
	// }
	// cout << endl;
	// for (int e : y) {
	// 	cout << e << " ";
	// }
	// cout << endl;
	answer(c, x, y);
}

#ifdef LC
#include "grader.cpp"
#endif

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