#include "doll.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 400000 + 10;
const int INF = 1e9;
int n, m, cnt;
std::vector <int> a, c, x, y;
int build(int l, int r, int excess)
{
if (r < excess)
{
return -1;
}
if (l == r)
{
return 0;
}
int node = ++cnt;
x.push_back(0);
y.push_back(0);
int mid = l + r >> 1;
x[node - 1] = build(l, mid, excess);
y[node - 1] = build(mid + 1, r, excess);
return -node;
}
bool state[MAXN];
bool push(int node, int value)
{
if (state[node] ? (y[node - 1] == -1) : (x[node - 1] == -1))
{
state[node] ^= 1;
return false;
}
if (state[node] ? (y[node - 1] == 0) : (x[node - 1] == 0))
{
if (state[node]) y[node - 1] = value;
else x[node - 1] = value;
state[node] ^= 1;
return true;
}
if (state[node])
{
bool res = push(-y[node - 1], value);
state[node] ^= 1;
return res;
} else
{
bool res = push(-x[node - 1], value);
state[node] ^= 1;
return res;
}
}
void create_circuit(int M, std::vector <int> A)
{
a = A;
m = M;
a.push_back(0);
int bits = 0;
int n = a.size();
while ((1 << bits) < n)
{
bits++;
}
build(0, (1 << bits) - 1, (1 << bits) - n);
for (int i = 0 ; i < n ; ++i)
{
while (!push(1, a[i]));
}
std::vector <int> c(m + 1, -1);
answer(c, x, y);
}
Compilation message
doll.cpp: In function 'int build(int, int, int)':
doll.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
29 ms |
5060 KB |
Output is correct |
3 |
Correct |
24 ms |
4996 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
1628 KB |
Output is correct |
6 |
Correct |
44 ms |
7136 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
29 ms |
5060 KB |
Output is correct |
3 |
Correct |
24 ms |
4996 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
1628 KB |
Output is correct |
6 |
Correct |
44 ms |
7136 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
57 ms |
8064 KB |
Output is correct |
9 |
Correct |
59 ms |
8572 KB |
Output is correct |
10 |
Correct |
89 ms |
12496 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
440 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
29 ms |
5060 KB |
Output is correct |
3 |
Correct |
24 ms |
4996 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
6 ms |
1628 KB |
Output is correct |
6 |
Correct |
44 ms |
7136 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
57 ms |
8064 KB |
Output is correct |
9 |
Correct |
59 ms |
8572 KB |
Output is correct |
10 |
Correct |
89 ms |
12496 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
440 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
87 ms |
11984 KB |
Output is correct |
15 |
Correct |
57 ms |
7536 KB |
Output is correct |
16 |
Correct |
87 ms |
11528 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
83 ms |
12044 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
444 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
54 ms |
6436 KB |
Output is correct |
3 |
Correct |
61 ms |
6516 KB |
Output is correct |
4 |
Correct |
84 ms |
9756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
54 ms |
6436 KB |
Output is correct |
3 |
Correct |
61 ms |
6516 KB |
Output is correct |
4 |
Correct |
84 ms |
9756 KB |
Output is correct |
5 |
Correct |
79 ms |
11008 KB |
Output is correct |
6 |
Correct |
81 ms |
10800 KB |
Output is correct |
7 |
Correct |
88 ms |
11012 KB |
Output is correct |
8 |
Correct |
95 ms |
10616 KB |
Output is correct |
9 |
Correct |
51 ms |
6772 KB |
Output is correct |
10 |
Correct |
79 ms |
10536 KB |
Output is correct |
11 |
Correct |
73 ms |
10032 KB |
Output is correct |
12 |
Correct |
48 ms |
6776 KB |
Output is correct |
13 |
Correct |
51 ms |
7280 KB |
Output is correct |
14 |
Correct |
49 ms |
7392 KB |
Output is correct |
15 |
Correct |
50 ms |
7284 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
44 ms |
7052 KB |
Output is correct |
18 |
Correct |
51 ms |
6860 KB |
Output is correct |
19 |
Correct |
51 ms |
6864 KB |
Output is correct |
20 |
Correct |
84 ms |
10288 KB |
Output is correct |
21 |
Correct |
84 ms |
10036 KB |
Output is correct |
22 |
Correct |
83 ms |
10048 KB |
Output is correct |