Submission #793911

#	Time	Username	Problem	Language	Result	Execution time	Memory
793911		Sohsoh84	Mechanical Doll (IOI18_doll)	C++17	100 / 100	72 ms	11892 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x)		(x).begin(), (x).end()
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;

int s = 1, n, fake_vert;
vector<int> C, X, Y, A;

inline int create_switch(int x, int y) {
	X.push_back(x);
	Y.push_back(y);
	s++;
	return -(s - 1);
}

inline int create_trigger(int x) {
	X.push_back(-s);
	Y.push_back(x);
	
	s++;
	return -(s - 1); 
}

int build(int l = 0, int r = n - 1) {
	if (A[l] == fake_vert && A[r] == fake_vert) return fake_vert;
	if (l == r) return A[l];
	else {
		int mid = (l + r) >> 1;
		int a = build(l, mid);
		int b = build(mid + 1, r);

		//cerr << l << sep << r << sep << -s << sep << a << sep << b << endl;
		return create_switch(a, b);
	}
}

inline int f(int ind, int lg) {
	int ans = 0;
	while (lg--) {
		ans = (ans << 1 | (ind & 1));
		ind >>= 1;
	}

	return ans;
}

inline void print() {
	debug("print")
	for (int i = 0; i < int(C.size()); i++)
		cerr << i << ": " << C[i] << endl;

	cerr << endl;
	cerr << endl;

	for (int i = 0; i < int(X.size()); i++)
		cerr << -(i + 1) << ": " <<  X[i] << sep << Y[i] << endl;

	cerr << endl;
	cerr << endl;
}

void create_circuit(int m, vector<int> A_) {
	A = A_;
	A.push_back(0);
	A_.push_back(0);

	C.resize(m + 1);
	C[0] = A.front();
	A.erase(A.begin());
	A_.erase(A_.begin());

	fake_vert = create_trigger(-1);		
	reverse(all(A));
	while (__builtin_popcount(int(A.size())) > 1) A.push_back(fake_vert);
	reverse(all(A));

	n = A.size();
	int lg = __builtin_ctz(n);

	vector<pair<int, int>> tmp;
	int ind = n - 1;
	while (ind >= 0 && A[ind] >= 0) {
		tmp.push_back({f(ind, lg), ind});
		ind--;
	}

	sort(all(tmp));	
	for (int i = 0; i < int(A_.size()); i++)
		A[tmp[i].second] = A_[i];

	int root = build(0, n - 1);
	Y[0] = root;

	while (A.back() < 0) A.pop_back();
	
	for (int i = 1; i <= m; i++) C[i] = root;

//	assert(X.size() <= 2 * n);
//	print();
	answer(C, X, Y);
}

// TODO: change destincation of fake_vert to root

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