#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bit(a , b) (((a)>>(b))&1)
const int maxn = 1e6 + 20;
const int maxb = 20;
int id , pt , R;
int x[maxn] , y[maxn];
vector<int> a , bits;
int build(int n)
{
if(n == 0)
return -1;
int root = id++;
x[root] = build(n - 1);
y[root] = build(n - 1);
return root;
}
int solve(int k)
{
while(k < bits[0]);
if(k == bits[0])
return build(k);
int xi = lower_bound(bits.begin() , bits.end() , k) - bits.begin();
if(xi == (int)bits.size())
cout << 1/0;
int root = id++;
if(bits[xi] == k)
{
x[root] = build(k);
y[root] = id;
x[id] = -1e9;
id++;
y[id - 1] = solve(k - 1);
}
else
{
y[root] = solve(k - 1);
x[root] = -1e9;
}
return root;
}
bool is[maxn];
void dfs(int v)
{
while(pt < (int)a.size())
{
if(!is[v])
{
is[v] ^= 1;
if(x[v] < 0)
x[v] = a[pt++] + maxn * 10 , v = R;
else
v = x[v];
}
else
{
is[v] ^= 1;
if(y[v] < 0)
y[v] = a[pt++] + maxn * 10 , v = R;
else
v = y[v];
}
}
}
void create_circuit(int m, vector<int> A)
{
memset(x , -1 , sizeof x);
memset(y , -1 , sizeof y);
a = A;
a.pb(0);
int n = a.size();
for(int j = 0; j < 20; j++)
if(bit(n , j))
bits.pb(j);
R = solve(bits.back());
for(int i = 0; i < id; i++)
if(x[i] < -maxn)
x[i] = R;
dfs(R);
for(int i = 0; i < id; i++)
{
int v = i;
if(x[v] >= maxn * 10)
x[v] = x[v] - maxn * 10;
else
x[v] = -x[v] - 1;
if(y[v] >= maxn * 10)
y[v] = y[v] - maxn * 10;
else
y[v] = -y[v] - 1;
}
vector<int> res;
for(int i = 0; i <= m; i++)
res.pb(-R - 1);
vector<int> X , Y;
for(int i = 0; i < id; i++)
X.pb(x[i]) , Y.pb(y[i]);
answer(res , X , Y);
}
Compilation message
doll.cpp: In function 'int solve(int)':
doll.cpp:38:12: warning: division by zero [-Wdiv-by-zero]
38 | cout << 1/0;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8060 KB |
Output is correct |
2 |
Correct |
69 ms |
11908 KB |
Output is correct |
3 |
Correct |
61 ms |
11688 KB |
Output is correct |
4 |
Correct |
7 ms |
8012 KB |
Output is correct |
5 |
Correct |
23 ms |
9412 KB |
Output is correct |
6 |
Runtime error |
48 ms |
18748 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8060 KB |
Output is correct |
2 |
Correct |
69 ms |
11908 KB |
Output is correct |
3 |
Correct |
61 ms |
11688 KB |
Output is correct |
4 |
Correct |
7 ms |
8012 KB |
Output is correct |
5 |
Correct |
23 ms |
9412 KB |
Output is correct |
6 |
Runtime error |
48 ms |
18748 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8060 KB |
Output is correct |
2 |
Correct |
69 ms |
11908 KB |
Output is correct |
3 |
Correct |
61 ms |
11688 KB |
Output is correct |
4 |
Correct |
7 ms |
8012 KB |
Output is correct |
5 |
Correct |
23 ms |
9412 KB |
Output is correct |
6 |
Runtime error |
48 ms |
18748 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8012 KB |
Output is correct |
2 |
Correct |
6 ms |
8052 KB |
Output is correct |
3 |
Correct |
8 ms |
8088 KB |
Output is correct |
4 |
Correct |
7 ms |
8012 KB |
Output is correct |
5 |
Correct |
7 ms |
8048 KB |
Output is correct |
6 |
Correct |
6 ms |
8012 KB |
Output is correct |
7 |
Correct |
5 ms |
8020 KB |
Output is correct |
8 |
Correct |
8 ms |
8072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
8044 KB |
Output is correct |
2 |
Correct |
87 ms |
12892 KB |
Output is correct |
3 |
Correct |
80 ms |
12828 KB |
Output is correct |
4 |
Runtime error |
84 ms |
21432 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
8044 KB |
Output is correct |
2 |
Correct |
87 ms |
12892 KB |
Output is correct |
3 |
Correct |
80 ms |
12828 KB |
Output is correct |
4 |
Runtime error |
84 ms |
21432 KB |
Execution killed with signal 11 |