Submission #231070

#	Time	Username	Problem	Language	Result	Execution time	Memory
231070		islingr	Mechanical Doll (IOI18_doll)	C++14	100 / 100	113 ms	11424 KiB

doll

// Iterative segtree implementation makes it easy to implement yay
#include "doll.h"
#include <iostream>
#include <vector>
using namespace std;
 #define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)

const int inf = 1e9, N = 1 << 18;
int tree[N << 1], rev[N];

void create_circuit(int m, vector<int> a) {
	a.eb(0); int n = a.size(), sz = 1;

	while (sz < n) sz <<= 1;
	rep(i, 0, sz) tree[i + sz] = inf;

	for (int i = 0, j = 0; i < sz; ++i) {
		rev[i] = rev[i >> 1];
		if (i & 1) rev[i] |= sz;
		rev[i] >>= 1;
		if (rev[i] < sz - n) continue;
		tree[rev[i] + sz] = a[j++];
	}

	int cnt = 0;
	vector<int> x, y;
	for (int i = sz; --i; )
		if (tree[i << 1 | 0] != tree[i << 1 | 1]) {
			tree[i] = -++cnt;
			x.eb(tree[i << 1|0]);
			y.eb(tree[i << 1|1]);
		} else tree[i] = tree[i << 1];

	rep(i, 0, cnt) {
		if (x[i] == inf) x[i] = tree[1];
		if (y[i] == inf) y[i] = tree[1];
	}
	answer(vector<int>(m + 1, tree[1]), x, y);
}

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