Submission #415616

#	Time	Username	Problem	Language	Result	Execution time	Memory
415616		_fractal	Mechanical Doll (IOI18_doll)	C++14	84 / 100	205 ms	262148 KiB

doll

#include "doll.h"
#include <iostream>

using namespace std;

vector<int> L, R, T, go, nw;
vector<int> inv, X, Y, del, pos;
int s;

void build(int v, int tl, int tr) {
	if (tl == tr)
		return;
	if (L[v] == 0)
		L[v] = ++s;
	if (R[v] == 0)
		R[v] = ++s;
	int tm = tl + tr >> 1;
	build(L[v], tl, tm);
	build(R[v], tm + 1, tr);
}

void upd(int pos, int val, int v, int tl, int tr) {
	if (tl == tr) {
		go[v] = val;
		T[v] = (val == 0);
		return void();
	}
	int tm = tl + tr >> 1;
	if (pos <= tm)
		upd(pos, val, L[v], tl, tm);
	else
		upd(pos, val, R[v], tm + 1, tr);
	T[v] = T[L[v]] + T[R[v]];
}

void clear(int v, int tl, int tr) {
	del[v] = 1;
	if (tl == tr)
		return;
	int tm = tl + tr >> 1;
	clear(L[v], tl, tm);
	clear(R[v], tm + 1, tr);
}

void make(int v, int tl, int tr) {
	int tm = tl + tr >> 1;
	if (T[L[v]] == tm - tl + 1) {
		clear(L[v], tl, tm);
		L[v] = 0;
	}
	if (T[R[v]] == tr - tm) {
		clear(R[v], tm + 1, tr);
		R[v] = 0;
	}
	if (tl == tm && L[v]) {
		del[L[v]] = 1;
		L[v] = go[L[v]];
	}
	if (tm + 1 == tr && R[v]) {
		del[R[v]] = 1;
		R[v] = go[R[v]];
	}
	if (tl == tr)
		return;
	if (L[v] > 0)
		make(L[v], tl, tm);
	if (R[v] > 0)
		make(R[v], tm + 1, tr);
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	vector<int> C(M + 1);
	int n = 1, len = 0;
	while (n < N) {
		n <<= 1;
		len++;
	}
	L.resize(n << 1), R.resize(n << 1), del.resize(n << 1), pos.resize(n << 1);
	T.resize(n << 1); go.resize(n << 1), nw.resize(n << 1);
	vector<int> inv(n, 0);
	build(0, 0, n - 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= len; ++j) {
			inv[i] |= (1 << (len - j - 1)) * ((i >> j) & 1);
		}
	}
	C[0] = A[0];
	A.erase(A.begin());
	A.push_back(0);
	for (int i = 0; i < n - N; ++i) {
		upd(i, 0, 0, 0, n - 1);
	}
	for (int i = n - N, col = 0; i < n; ++i) {
		pos[inv[i]] = 1;
	}
	for (int i = 0, col = 0; i < n; ++i) {
		if (pos[i] == 1)
			pos[i] = col++;
	}
	for (int i = n - N; i < n; ++i) {
		upd(i, -A[pos[inv[i]]] - 1, 0, 0, n - 1);
	}
	make(0, 0, n - 1);
	for (int i = 0, is = 0; i <= s; ++i) {
		if (del[i]) {
			continue;
		}
		is--;
		nw[i] = is;
	}
	for (int v = 0; v <= s; ++v) {
		if (del[v]) {
			continue;
		}
		if (L[v] >= 0)
			X.push_back(nw[L[v]]);
		else
			X.push_back(-L[v] - 1);
		if (R[v] >= 0)
			Y.push_back(nw[R[v]]);
		else
			Y.push_back(-R[v] - 1);
	}
	for (int i = 1; i <= M; ++i)
		C[i] = -1;
	answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void build(int, int, int)':
doll.cpp:17:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
doll.cpp: In function 'void upd(int, int, int, int, int)':
doll.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
doll.cpp: In function 'void clear(int, int, int)':
doll.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
doll.cpp: In function 'void make(int, int, int)':
doll.cpp:46:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:94:22: warning: unused variable 'col' [-Wunused-variable]
   94 |  for (int i = n - N, col = 0; i < n; ++i) {
      |                      ^~~

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