#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define vll vector<int>
#define ll int
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
vector<int> XP,YP;
const int NM=1e6+10;
ll cp[NM],label=0,father_of_all=-1;
vll fast_order(ll n)
{
if(n==2)
return {1,2};
vll ans;
ll hn=n/2;
for(int i=1;i<=n;i+=2)
ans.pb(i);
vll hans(hn);
vll np=fast_order(n/2);
for(int j=0;j<hn;j++)
hans[np[j]-1]=ans[j];
ans.clear();
for(auto i:hans)
ans.pb(i);
for(auto i:hans)
ans.pb(i+1);
return ans;
}
vll childx,childy,order_,npp;
int label_it(vll&p,int l,int r,bool lp=0)
{
if((l-r)==0){
if(p[l]==-NM)
{
return father_of_all;
}
return p[l];
}
int mid=(l+r)/2;
bool use=0;
for(int i=l;i<=r;i++)
{
if(p[i]!=-NM)
{
use=1;
break;
}
}
label++;
int usep=-label;
int fk=-1;
if(!use)
{
fk=childx.size();
childx.pb(father_of_all);
childy.pb(father_of_all);
}
else
{
int lc=label_it(p,l,mid,1);
int rc=label_it(p,mid+1,r,1);
fk=childx.size();
childx.pb(lc);
childy.pb(rc);
}
order_.pb(fk);
npp.pb(usep);
return usep;
}
vll child_[NM];
ll fake_id=0,state[NM],req_sz=0;
int label_it_fake(vll&p,int l,int r,bool lp=0)
{
// cout<<"Range "<<l<<' '<<r<<' '<<" p: ";
// for(int i=l;i<=r;i++)
// {
// cout<<p[i]<<' ';
// }
// cout<<endl;
if((l-r)==0){
if(p[l]==-NM)
return 0;
req_sz++;
// cout<<"Label: "<<-l-1<<endl;
return -l-1; // always negative
}
int mid=(l+r)/2;
bool use=0;
for(int i=l;i<=r;i++)
{
if(p[i]!=-NM)
{
use=1;
break;
}
}
int fk=fake_id;
fake_id++;
child_[fk].clear();
state[fk]=0;
if(!use)
{
// all minus one is subtree
// cout<<"Node "<<fk<<endl;
// cout<<"Child: "<<0<<' '<<0<<endl;
child_[fk].pb(0);
child_[fk].pb(0);
}
else
{
int lc=label_it_fake(p,l,mid,1);
int rc=label_it_fake(p,mid+1,r,1);
child_[fk].pb(lc);
child_[fk].pb(rc);
// cout<<"Node "<<fk<<endl;
// cout<<"Child: "<<lc<<' '<<rc<<endl;
// cout<<"Range "<<l<<' '<<r<<endl;
// cout<<"Child: "<<XP.back()<<' '<<YP.back()<<endl;
}
// cout<<"Assigned to range "<<l<<' '<<r<<' ';
// cout<<fk<<endl;
return fk;
}
vll my_order;
void generate_order(int cur)
{
if(my_order.size()==req_sz)return;
// cout<<"At "<<cur<<endl;
if(cur<0)
{
// cout<<"Pushing "<<cur<<endl;
my_order.push_back(cur);
generate_order(0);
return;
}
state[cur]=1-state[cur];
generate_order(child_[cur][1-state[cur]]);
}
void create_circuit(int m, std::vector<int> a)
{
XP.clear();
YP.clear();
label=0;
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
{
int v=a[0];
child[0].push_back(v);
for(int j=1;j<a.size();j++)
child[v].push_back(a[j]);
child[v].push_back(0);
int lps=0;
for(int j=0;j<=m;j++)
ans[j]=-1;
// cout<<"SZ: "<<child[v].size()<<endl;
for(auto i:{0,v})
{
if(child[i].size()==0)continue;
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else
{
ll pw=1;
while(child[i].size()>pw)
pw*=2;
int zxp=child[i].size();
vll fl(pw);
for(int j=0;j<zxp;j++)
fl[j]=child[i][j];
for(int j=zxp;j<pw;j++)
fl[j]=-NM;
// cout<<"After\n";
// for(int j=0;j<pw;j++)
// {
// cout<<fl[j]<<' ';
// }
// cout<<endl;
father_of_all=-label-1;
childx.clear();
childy.clear();
order_.clear();
npp.clear();
ll og=label;
father_of_all=-label-1;
// pw then
// cout<<"Father "<<father_of_all<<endl;
// cout<<"Do label\n";
childx.clear();
childy.clear();
order_.clear();
npp.clear();
req_sz=0;
my_order.clear();
fake_id=0;
int root=label_it_fake(fl,0,pw-1);
// cout<<"Made the fake tree\n";
// for(int j=0;j<fake_id;j++)
// {
// cout<<"Had node "<<j<<endl;
// cout<<"Adj: ";
// for(auto k:child_[j])
// {
// cout<<k<<' ';
// }
// cout<<endl;
// }
generate_order(root);
// cout<<"My Order: ";
for(auto j:my_order)
// cout<<j<<' ';
// cout<<endl;
// cout<<"Req order: ";
// for(auto j:child[i])
// {
// cout<<j<<' ';
// }
// cout<<endl;
for(int i=0;i<pw;i++)fl[i]=-NM;
for(int k=0;k<child[i].size();k++)
{
fl[-my_order[k]-1]=child[i][k];
}
// cout<<"Before\n";
// for(int i=0;i<pw;i++)
// {
// cout<<fl[i]<<' ';
// }
// cout<<endl;
label_it(fl,0,pw-1);
ll last=XP.size();
for(int i=0;i<order_.size();i++)
{
XP.pb(0);
YP.pb(0);
}
for(int i=0;i<order_.size();i++)
{
ll cur=-og-npp[i]-1;
XP[last+cur]=(childx[i]);
YP[last+cur]=(childy[i]);
}
ans[i]=father_of_all;
}
}
// cout<<"ans\n";
// for(int i=0;i<=m;i++)
// {
// cout<<i<<' '<<ans[i]<<' '<<'Z'<<endl;;
// }
// cout<<endl;
// cout<<"xy\n";
// cout<<XP.size()<<endl;
// cout<<YP.size()<<endl;
// for(auto i:XP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(auto i:YP)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// for(int i=0;i<label;i++)
// {
// cout<<-i-1<<' '<<XP[i]<<' '<<'X'<<endl;
// cout<<-i-1<<' '<<YP[i]<<' '<<'Y'<<endl;
// // cout<<XP[i]<<' '<<YP[i]<<endl;
// }
answer(ans,XP,YP);
}
}
Compilation message
doll.cpp: In function 'void generate_order(int)':
doll.cpp:127:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
127 | if(my_order.size()==req_sz)return;
| ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:150:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int j=1;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:167:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
167 | while(child[i].size()>pw)
| ~~~~~~~~~~~~~~~^~~
doll.cpp:212:14: warning: unused variable 'j' [-Wunused-variable]
212 | for(auto j:my_order)
| ^
doll.cpp:222:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
222 | for(int k=0;k<child[i].size();k++)
| ~^~~~~~~~~~~~~~~~
doll.cpp:234:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:239:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
239 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:153:7: warning: unused variable 'lps' [-Wunused-variable]
153 | int lps=0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
25436 KB |
state 'Y' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
25436 KB |
state 'Y' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
25436 KB |
state 'Y' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
25432 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25436 KB |
Output is correct |
| 3 |
Correct |
9 ms |
25324 KB |
Output is correct |
| 4 |
Correct |
9 ms |
25436 KB |
Output is correct |
| 5 |
Correct |
10 ms |
25436 KB |
Output is correct |
| 6 |
Correct |
10 ms |
25436 KB |
Output is correct |
| 7 |
Correct |
9 ms |
25436 KB |
Output is correct |
| 8 |
Correct |
10 ms |
25688 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
25388 KB |
state 'Y' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
10 ms |
25388 KB |
state 'Y' |
| 2 |
Halted |
0 ms |
0 KB |
- |
