Submission #1195445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195445		stdfloat	자동 인형 (IOI18_doll)	C++20	100 / 100	152 ms	20148 KiB

doll

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

#define sz(v) (int)v.size()

int lg, lmt, ind;

vector<bool> need, R;

vector<int> a, v, C;

void f(int x, int l) {
	if (l == lg + 1) {
		x = -x;
		v[x] = a[ind++];

		if (!v[x]) {
			map<int, int> m;
			for (int i = 1; i <= lmt; i++)
				if (need[i] && !~v[i]) m[i] = sz(m) + 1;

			vector<int> X(sz(m)), Y(sz(m));
			for (int i = 1; i <= lmt; i++) {
				if (need[i] && !~v[i]) {
					int ch = i << 1;
					Y[m[i] - 1] = (~v[ch] ? v[ch] : -m[ch]);
					X[m[i] - 1] = (~v[ch + 1] ? v[ch + 1] : -(!need[ch + 1] ? 1 : m[ch + 1]));
				}
			}

			answer(C, X, Y);

			return;
		}

		return f(-1, 0), void();
	}

	x = -x;
	int ch = x << 1;
	
	if (R[x]) {
		R[x] = false;
		if (!need[ch + 1]) f(-1, 0);
		else f(-(ch + 1), l + 1);
	}
	else {
		R[x] = true;
		f(-ch, l + 1);
	}
}

void create_circuit(int m, vector<int> A) {
	if (sz(A) == 1) {
		vector<int> C(m + 1);
		C[0] = A[0];
		return answer(C, {}, {}), void();
	}

	a = A;
	C.assign(m + 1, -1); C[0] = a[0];
	a.erase(a.begin());
	a.push_back(0);

	int n = sz(a);

	lg = __lg(n - 1);
	lmt = (1 << (lg + 1)) + n - 1;

	need.assign(1 << (lg + 2), 0);
	for (int i = 1; i <= lmt; i++) {
		int x = i;
		for (int j = 0; j <= lg - __lg(i) && x <= lmt; j++)
			x <<= 1;

		need[i] = x <= lmt;
	}

	R.assign(lmt + 1, true);
	v.assign(1 << (lg + 2), -1);
	f(-1, 0);
}

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