oj.uz

Submission #415618

# Submission time Handle Problem Language Result Execution time Memory
415618 2021-06-01T09:47:06 Z _fractal Mechanical Doll (IOI18_doll) C++14
100 / 100
 171 ms 37516 KB 
#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);
	if (N == 1) {
		C[0] = A[0];
		C[A[0]] = 0;
		answer(C, {}, {});
		return;
	}
	int n = 1, len = 0;
	while (n < N) {
		n <<= 1;
		len++;
	}
	n *= 2;
	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);
	n /= 2;
	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

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:102:22: warning: unused variable 'col' [-Wunused-variable]
  102 |  for (int i = n - N, col = 0; i < n; ++i) {
      |                      ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 11112 KB Output is correct
3 Correct 75 ms 18004 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 83 ms 19684 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 11112 KB Output is correct
3 Correct 75 ms 18004 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 83 ms 19684 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 20088 KB Output is correct
9 Correct 139 ms 35452 KB Output is correct
10 Correct 160 ms 37516 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 11112 KB Output is correct
3 Correct 75 ms 18004 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 83 ms 19684 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 20088 KB Output is correct
9 Correct 139 ms 35452 KB Output is correct
10 Correct 160 ms 37516 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 164 ms 37132 KB Output is correct
15 Correct 133 ms 34668 KB Output is correct
16 Correct 171 ms 36852 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 169 ms 37184 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 85 ms 19504 KB Output is correct
3 Correct 122 ms 34072 KB Output is correct
4 Correct 151 ms 36444 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 85 ms 19504 KB Output is correct
3 Correct 122 ms 34072 KB Output is correct
4 Correct 151 ms 36444 KB Output is correct
5 Correct 154 ms 36736 KB Output is correct
6 Correct 156 ms 36572 KB Output is correct
7 Correct 165 ms 36584 KB Output is correct
8 Correct 164 ms 36528 KB Output is correct
9 Correct 134 ms 34096 KB Output is correct
10 Correct 153 ms 36424 KB Output is correct
11 Correct 157 ms 36424 KB Output is correct
12 Correct 132 ms 34144 KB Output is correct
13 Correct 86 ms 19484 KB Output is correct
14 Correct 136 ms 34472 KB Output is correct
15 Correct 133 ms 34652 KB Output is correct
16 Correct 5 ms 1356 KB Output is correct
17 Correct 87 ms 19412 KB Output is correct
18 Correct 86 ms 19512 KB Output is correct
19 Correct 146 ms 34192 KB Output is correct
20 Correct 165 ms 36496 KB Output is correct
21 Correct 153 ms 36512 KB Output is correct
22 Correct 154 ms 36372 KB Output is correct