Submission #604920

#	Time	Username	Problem	Language	Result	Execution time	Memory
604920		DanShaders	Mechanical Doll (IOI18_doll)	C++17	70.67 / 100	128 ms	11716 KiB

doll

//Dgrader.cpp
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 4e5 + 10;

pair<int, int> switches[N];
int next_free = 1;

int create(vector<int> a) {
	int result = next_free++;
	if (sz(a) == 1) {
		switches[result] = {-result, a[0]};
	} else if (sz(a) == 2) {
		switches[result] = {a[0], a[1]};
	} else {
		vector<int> left, right;
		for (int i = 0; i < sz(a); ++i) {
			(i % 2 ? right : left).push_back(a[i]);
		}
		switches[result] = {
			(count(all(left), -1) == sz(left)) ? -1 : -create(left),
			(count(all(right), -1) == sz(right)) ? -1 : -create(right)
		};
	}
	return result;
}

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	int nsize = sz(a);
	while (nsize & (nsize - 1)) {
		++nsize;
	}
	vector<int> usable(nsize, -1);
	int n = __builtin_ctz(nsize);
	for (int i = 0; i < sz(a) - 1; ++i) {
		int where = 0;
		for (int j = 0; j < n; ++j) {
			where |= (i >> j & 1) << (n - j - 1);
		}
		usable[where] = 0;
	}
	usable.back() = 0;
	for (int i = 0, it = 0; i < nsize; ++i) {
		if (usable[i] == 0) {
			usable[i] = a[it++];
		}
	}
	// for (int u : usable) {
	// 	cout << u << " ";
	// }
	// cout << endl;
	create(usable);
	vector<int> xs, ys;
	for (int i = 1; i < next_free; ++i) {
		xs.push_back(switches[i].x);
		ys.push_back(switches[i].y);

	}
	answer(vector<int>(m + 1, -1), xs, ys);
}

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