Submission #788277

#	Time	Username	Problem	Language	Result	Execution time	Memory
788277		pavement	Mechanical Doll (IOI18_doll)	C++17	9 / 100	58 ms	11868 KiB

doll

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

using ii = pair<int, int>;

#define pb push_back
#define eb emplace_back

vector<ii> construct(int x) {
	assert(x >= 2);
	if (x == 2) {
		vector<ii> ret;
		ret.eb(-1, -1);
		return ret;
	}
	// construct a sequence of switches that goes to exactly x outputs
	if (x % 2 == 0) {
		auto lh = construct(x / 2), rh = lh;
		// relabel nodes in rh
		for (auto &i : rh) {
			if (i.first != -1) i.first += lh.size();
			if (i.second != -1) i.second += lh.size();
		}
		vector<ii> lrh;
		for (auto i : lh) lrh.pb(i);
		for (auto i : rh) lrh.pb(i);
		// create new switch
		lrh.eb(lh.size() - 1, lh.size() + rh.size() - 1);
		return lrh;
	} else {
		auto lh = construct((x + 1) / 2), rh = lh;
		// relabel nodes in rh
		for (auto &i : rh) {
			if (i.first != -1) i.first += lh.size();
			if (i.second != -1) i.second += lh.size();
		}
		// reroute last switch of left half
		for (int i = (int)lh.size() - 1; i >= 0; i--) {
			if (lh[i].second == -1) {
				lh[i].second = lh.size() * 2;
				break;
			}
		}
		vector<ii> lrh;
		for (auto i : lh) lrh.pb(i);
		for (auto i : rh) lrh.pb(i);
		// create new switch
		lrh.eb(lh.size() - 1, lh.size() + rh.size() - 1);
		return lrh;
	}
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> C, X, Y;
	auto XY = construct(N);
	for (auto &i : XY) {
		if (i.first == -1) i.first = 1;
		else i.first = -(i.first + 1);
		if (i.second == -1) i.second = 1;
		else i.second = -(i.second + 1);
	}
	for (auto i : XY) {
		X.pb(i.first);
		Y.pb(i.second);
	}
	C.pb(1);
	C.pb(-X.size());
	for (int i = (int)Y.size() - 1; i >= 0; i--) {
		if (Y[i] == 1) {
			Y[i] = 0;
			break;
		}
	}
	answer(C, X, Y);
}

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