Submission #297784

#	Time	Username	Problem	Language	Result	Execution time	Memory
297784		ChrisT	Mechanical Doll (IOI18_doll)	C++17	100 / 100	168 ms	8412 KiB

doll

#include <bits/stdc++.h>
#include "doll.h" 
using namespace std;
void create_circuit (int m, vector<int> a) {
	a.push_back(0);
	int n = (int)a.size(), go = 1 << (__lg(n - 1) + 1), cur = 1; ++m;
	vector<int> c(m), x(1), y(1);
	iota(c.begin(),c.end(),0); c[0] = -1;
	vector<int> order;
	auto get = [&] (int l, int r, int ind, int dep, const auto &ref) -> void {
		if (l == r) {
			if (l - go + n >= 0) order.push_back(ind);
			return;
		}
		int mid = (l + r) / 2;
		ref(l,mid,ind,dep+1,ref); ref(mid+1,r,ind|(1<<dep),dep+1,ref); 
	};
	get(0,go-1,0,0,get);
	sort(order.begin(),order.end());
	auto build = [&] (int l, int r, int ind, int dep, const auto &ref) -> int {
		if (l == r) {
			if (l - go + n < 0) return -1;
			int want = lower_bound(order.begin(),order.end(),ind) - order.begin();
			c[a[want]] = -1;
			return a[want];
		}
		int mid = (l + r) / 2;
		int lc = ref(l,mid,ind,dep+1,ref), rc = ref(mid+1,r,ind | (1 << dep),dep+1,ref);
		if (lc == rc) return lc;
		x.push_back(lc); y.push_back(rc);
		return -(++cur);
	};
	x[0] = build(0,go/2-1,0,1,build); y[0] = build(go/2,go-1,1,1,build);
	answer(c,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