Submission #230747

#	Time	Username	Problem	Language	Result	Execution time	Memory
230747		islingr	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	204 KiB

doll

// So annoying to implement
#include "doll.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define eb(x...) emplace_back(x)
#define sz(x) int((x).size())

using vi = vector<int>;

const int inf = 1e9;

vi x, y;

int p(const int& x) {
	int ret = 0;
	while ((1 << ret) < x) ++ret;
	return ret;
}

int cntr = 1;
template<class it>
void f(it st, it en, int i, int d, const vi &a) {
	int l = en - st;
	if (d == 1) {
		assert(l == 1 || l == 2);
		x[i] = a[*st];
		y[i] = l == 1 ? -1 : a[*(st + 1)];
	} else if (p(l) == d) {
		x[i] = -++cntr;
		int r = 1 << (d - 1);
		f(st, st + r, cntr, d - 1, a);
		y[i] = -++cntr;
		f(st + r, en, cntr, d - 1, a);
	} else {
		assert(p(l) < d);
		x[i] = -++cntr;
		f(st, en, cntr, d - 1, a);
		y[i] = -1;
	}
}

void create_circuit(int m, vi a) {
	a.eb(0); int n = a.size();

	int k = p(n), sz = 1 << k;
	vi rev(sz);
	rep(i, 0, sz) rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
	rev.resize(n);
	vi tmp(rev); sort(all(tmp));
	trav(x, rev) x = lb(all(tmp), x) - begin(tmp);

	x.resize(2 * sz, inf); y.resize(2 * sz, inf);
	f(all(rev), 1, k, a);
	while (x.back() == inf) x.pop_back();
	while (y.back() == inf) y.pop_back();
	x.erase(begin(x)); y.erase(begin(y));
	
	vi c(m + 1); sort(all(a));
	c[0] = -1;
	rep(i, 0, m) c[i + 1] = binary_search(all(a), i + 1) ? -1 : 0;
	answer(c, x, y);
}

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