oj.uz

Submission #526242

# Submission time Handle Problem Language Result Execution time Memory
526242 2022-02-14T03:44:00 Z ntabc05101 Mechanical Doll (IOI18_doll) C++14
100 / 100
 107 ms 9776 KB 
//why am i so stupid?

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

const int mxN = 1 << 18;

int n, p = 1, cr = 0;
vector<int> x(mxN), y(mxN);
bool e[mxN];

int bld(int l, int r) {
	if (l >= r) {
		return 0;
	}
	if (r < p - n) {
		return -1;
	}

	int z = ++cr, mid = l + r >> 1;
	x[z - 1] = bld(l, mid);
	y[z - 1] = bld(mid + 1, r);
	return -z;
}

void ptr(int z, int t) {
	auto &a = e[-z - 1] ? y[-z - 1]: x[-z - 1];
	e[-z - 1] ^= 1;
	if (!a) {
		a = t;
	}
	else {
		ptr(a, t);
	}
}

void create_circuit(int m, vector<int> a) {
	n = a.size();
	for (; p < n; p <<= 1);

	bld(0, p - 1);
	for (int i = 1; i < n; i++) {
		ptr(-1, a[i]);
	}
	if (n & 1) {
		ptr(-1, -1);
	}
	ptr(-1, 0);

	vector<int> c(m + 1, -1);
	c[0] = a[0];
	x.resize(cr + 1);
	y.resize(cr + 1);

	answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int bld(int, int)':
doll.cpp:21:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |  int z = ++cr, mid = l + r >> 1;
      |                      ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2296 KB Output is correct
2 Correct 35 ms 5124 KB Output is correct
3 Correct 35 ms 4744 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 11 ms 3524 KB Output is correct
6 Correct 56 ms 5964 KB Output is correct
7 Correct 1 ms 2252 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2296 KB Output is correct
2 Correct 35 ms 5124 KB Output is correct
3 Correct 35 ms 4744 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 11 ms 3524 KB Output is correct
6 Correct 56 ms 5964 KB Output is correct
7 Correct 1 ms 2252 KB Output is correct
8 Correct 64 ms 7244 KB Output is correct
9 Correct 76 ms 7624 KB Output is correct
10 Correct 104 ms 9776 KB Output is correct
11 Correct 1 ms 2252 KB Output is correct
12 Correct 1 ms 2376 KB Output is correct
13 Correct 2 ms 2252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2296 KB Output is correct
2 Correct 35 ms 5124 KB Output is correct
3 Correct 35 ms 4744 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 11 ms 3524 KB Output is correct
6 Correct 56 ms 5964 KB Output is correct
7 Correct 1 ms 2252 KB Output is correct
8 Correct 64 ms 7244 KB Output is correct
9 Correct 76 ms 7624 KB Output is correct
10 Correct 104 ms 9776 KB Output is correct
11 Correct 1 ms 2252 KB Output is correct
12 Correct 1 ms 2376 KB Output is correct
13 Correct 2 ms 2252 KB Output is correct
14 Correct 107 ms 9544 KB Output is correct
15 Correct 66 ms 6860 KB Output is correct
16 Correct 102 ms 9360 KB Output is correct
17 Correct 2 ms 2252 KB Output is correct
18 Correct 1 ms 2252 KB Output is correct
19 Correct 1 ms 2252 KB Output is correct
20 Correct 106 ms 9668 KB Output is correct
21 Correct 1 ms 2252 KB Output is correct
22 Correct 1 ms 2252 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct
2 Correct 60 ms 5572 KB Output is correct
3 Correct 64 ms 5560 KB Output is correct
4 Correct 95 ms 7236 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2252 KB Output is correct
2 Correct 60 ms 5572 KB Output is correct
3 Correct 64 ms 5560 KB Output is correct
4 Correct 95 ms 7236 KB Output is correct
5 Correct 103 ms 7760 KB Output is correct
6 Correct 98 ms 7780 KB Output is correct
7 Correct 99 ms 7876 KB Output is correct
8 Correct 102 ms 7600 KB Output is correct
9 Correct 61 ms 5568 KB Output is correct
10 Correct 97 ms 7452 KB Output is correct
11 Correct 106 ms 7236 KB Output is correct
12 Correct 63 ms 5564 KB Output is correct
13 Correct 63 ms 5816 KB Output is correct
14 Correct 65 ms 5928 KB Output is correct
15 Correct 70 ms 6064 KB Output is correct
16 Correct 3 ms 2380 KB Output is correct
17 Correct 58 ms 5560 KB Output is correct
18 Correct 59 ms 5556 KB Output is correct
19 Correct 64 ms 5568 KB Output is correct
20 Correct 98 ms 7316 KB Output is correct
21 Correct 96 ms 7188 KB Output is correct
22 Correct 96 ms 7244 KB Output is correct