Submission #753957

#	Time	Username	Problem	Language	Result	Execution time	Memory
753957		valerikk	Mechanical Doll (IOI18_doll)	C++17	100 / 100	158 ms	19924 KiB

doll

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

using namespace std;

namespace {

const int N = 6e5 + 501;

int n, m;
int pw;
vector<int> a;
int n1;
int x[N], y[N];
vector<int> kek;
int pos[N], f[N];
int fuck[N];

int dfs(int v) {
	if (n1 == 0) {
		return 1;
	}
	kek.push_back(v);
	if (v < (1 << pw)) {
		y[v] = dfs(2 * v + 1);
		x[v] = dfs(2 * v);
	} else {
		--n1;
	}
	return v;
}

}

void create_circuit(int m1, vector<int> a1) {
	m = m1;
	a = a1;
	n = a.size() + 1;
	a.push_back(0);
	pw = 0;
	while ((1 << pw) < n) {
		++pw;
	}
	vector<int> ord;
	{
		int v = 1;
		while ((int)ord.size() < (1 << pw)) {
			if (v >= (1 << pw)) {
				ord.push_back(v);
				v = 1;
			} else {
				f[v] ^= 1;
				if (f[v]) {
					v = 2 * v;
				} else {
					v = 2 * v + 1;
				}
			}
		}
	}
	assert((int)ord.size() == (1 << pw));
	for (int i = 0; i < (1 << pw); ++i) {
		pos[ord[i]] = i;
	}
	n1 = n;
	dfs(1);
	vector<int> lol, rofl;
	for (int v : kek) {
		if (v < (1 << pw)) {
			lol.push_back(v);
		} else {
			rofl.push_back(v);
		}
	}
	assert((int)rofl.size() == n);
	sort(rofl.begin(), rofl.end(), [&](int v, int u) {
		return pos[v] < pos[u];
	});
	// for (int v : rofl) {
	// 	cout << v << " ";
	// }
	// cout << endl;
	// for (int i = 0; i < n; ++i) {
	// 	cout << a[i] << " ";
	// }
	// cout << endl;
	for (int i = 0; i < n; ++i) {
		fuck[rofl[i]] = a[i];
	}
	vector<int> c(m + 1, -1);
	sort(lol.begin(), lol.end());
	int s = lol.size();
	vector<int> x1(s), y1(s);
	for (int i = 0; i < s; ++i) {
		int v = lol[i];
		// if (i == 3) {
		// 	cout << v << " " << x[v] << " " << y[v] << endl;
		// 	cout << fuck[x[v]] << " " << fuck[y[v]] << endl;
		// }
		if (x[v] >= (1 << pw)) {
			x1[i] = fuck[x[v]];
		} else {
			x1[i] = lower_bound(lol.begin(), lol.end(), x[v]) - lol.begin();
			x1[i] = -(x1[i] + 1);
		}
		if (y[v] >= (1 << pw)) {
			y1[i] = fuck[y[v]];
		} else {
			y1[i] = lower_bound(lol.begin(), lol.end(), y[v]) - lol.begin();
			y1[i] = -(y1[i] + 1);
		}
	}
	answer(c, x1, y1);
}

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