#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int n, m;
vector < int > g[maxn];
vector < int > c, x, y;
struct state
{
int dev, lf_child, rf_child;
vector < int > fin;
state()
{
dev = 0;
lf_child = rf_child = -1;
fin.clear();
}
};
void create_node(int v)
{
if (g[v].size() == 0)
return;
if (g[v].size() == 1)
{
c[v] = g[v][0];
return;
}
int nec = 2, st = 0;
while(nec < g[v].size())
nec *= 2, st ++;
///cout << g[v].size() << " " << nec << " : " << st << endl;
vector < state > gen;
int sz = x.size();
state it;
it.dev = ++ sz;
c[v] = -it.dev;
it.fin.push_back(1);
gen.push_back(it);
for (int step = 0; step < st; step ++)
{
vector < state > new_gen;
for (int i = 0; i < gen.size(); i ++)
{
state new_state;
new_state.dev = ++ sz;
gen[i].lf_child = - new_state.dev;
for (int cur : gen[i].fin)
new_state.fin.push_back(cur);
new_gen.push_back(new_state);
new_state = state();
new_state.dev = ++ sz;
gen[i].rf_child = - new_state.dev;
for (int cur : gen[i].fin)
new_state.fin.push_back(cur + (1 << step));
new_gen.push_back(new_state);
}
for (state cur : gen)
{
x.push_back(cur.lf_child);
y.push_back(cur.rf_child);
}
gen = new_gen;
}
///cout << "fine" << endl;
int offset = gen.size() * 2 - g[v].size();
int to = 0;
vector < int > vec;
for (int i = gen.size() - 1; i >= 0; i --)
{
int lf_path = gen[i].fin[0], rf_path = gen[i].fin[0] + (1 << st);
if (vec.size() < g[v].size())
vec.push_back(rf_path);
if (vec.size() < g[v].size())
vec.push_back(lf_path);
}
sort(vec.begin(), vec.end());
map < int, int > mp;
for (int i = 0; i < vec.size(); i ++)
{
mp[vec[i]] = i + 1;
}
for (int i = 0; i < gen.size(); i ++)
{
///cout << gen[i].fin.size() << endl;
int lf_path = gen[i].fin[0], rf_path = gen[i].fin[0] + (1 << st);
if (mp[lf_path] == 0)
x.push_back(-it.dev);
else
x.push_back(g[v][mp[lf_path] - 1]);
if (mp[rf_path] == 0)
y.push_back(-it.dev);
else
y.push_back(g[v][mp[rf_path] - 1]);
///cout << v << " :: " << lf_path << " : " << rf_path << endl;
/**if (to < g[v].size())
x.push_back(g[v][to] ++);
else
x.push_back(- it.dev);
if (rf_path > offset)
y.push_back(g[v][rf_path - offset - 1]);
else
y.push_back(-it.dev);*/
}
}
void create_circuit(int M, vector<int> A)
{
n = A.size();
m = M;
c.resize(m + 1);
g[0].push_back(A[0]);
for (int i = 1; i < A.size(); i ++)
{
g[0].push_back(A[i]);
}
g[0].push_back(0);
create_node(0);
for (int i = 0; i <= m; i ++)
c[i] = -1;
/**for (int i = 0; i <= m; i ++)
{
create_node(i);
continue;
}*/
/**for (int i = 0; i <= m; i ++)
cout << c[i] << " ";
cout << endl;
for (int i = 0; i < x.size(); i ++)
cout << x[i] << " " << y[i] << endl;*/
answer(c, x, y);
}
Compilation message
doll.cpp: In function 'void create_node(int)':
doll.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(nec < g[v].size())
| ~~~~^~~~~~~~~~~~~
doll.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 0; i < gen.size(); i ++)
| ~~^~~~~~~~~~~~
doll.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < vec.size(); i ++)
| ~~^~~~~~~~~~~~
doll.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < gen.size(); i ++)
| ~~^~~~~~~~~~~~
doll.cpp:73:9: warning: unused variable 'offset' [-Wunused-variable]
73 | int offset = gen.size() * 2 - g[v].size();
| ^~~~~~
doll.cpp:74:9: warning: unused variable 'to' [-Wunused-variable]
74 | int to = 0;
| ^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 1; i < A.size(); i ++)
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
2 |
Partially correct |
241 ms |
31092 KB |
Output is partially correct |
3 |
Partially correct |
230 ms |
31124 KB |
Output is partially correct |
4 |
Partially correct |
334 ms |
31860 KB |
Output is partially correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
3 ms |
4948 KB |
Output is partially correct |
2 |
Partially correct |
241 ms |
31092 KB |
Output is partially correct |
3 |
Partially correct |
230 ms |
31124 KB |
Output is partially correct |
4 |
Partially correct |
334 ms |
31860 KB |
Output is partially correct |
5 |
Partially correct |
324 ms |
32040 KB |
Output is partially correct |
6 |
Partially correct |
335 ms |
31960 KB |
Output is partially correct |
7 |
Partially correct |
323 ms |
32080 KB |
Output is partially correct |
8 |
Partially correct |
362 ms |
32008 KB |
Output is partially correct |
9 |
Partially correct |
263 ms |
31120 KB |
Output is partially correct |
10 |
Partially correct |
349 ms |
31996 KB |
Output is partially correct |
11 |
Partially correct |
317 ms |
31864 KB |
Output is partially correct |
12 |
Partially correct |
239 ms |
31120 KB |
Output is partially correct |
13 |
Partially correct |
235 ms |
31144 KB |
Output is partially correct |
14 |
Partially correct |
239 ms |
31152 KB |
Output is partially correct |
15 |
Partially correct |
244 ms |
31252 KB |
Output is partially correct |
16 |
Partially correct |
8 ms |
5808 KB |
Output is partially correct |
17 |
Correct |
132 ms |
19308 KB |
Output is correct |
18 |
Partially correct |
261 ms |
31116 KB |
Output is partially correct |
19 |
Partially correct |
237 ms |
31168 KB |
Output is partially correct |
20 |
Partially correct |
307 ms |
31960 KB |
Output is partially correct |
21 |
Partially correct |
316 ms |
31888 KB |
Output is partially correct |
22 |
Partially correct |
339 ms |
31888 KB |
Output is partially correct |