#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)
{
if((l-r)==0){
if(p[l]==-NM)
return 0;
req_sz++;
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)
{
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);
}
return fk;
}
vll my_order;
void generate_order(int cur)
{
if(my_order.size()==req_sz)return;
if(cur<0)
{
my_order.push_back(cur);
generate_order(0);
return;
}
state[cur]=1-state[cur];
generate_order(child_[cur][1-state[cur]]);
}
bool check(int m,vector<int> a)
{
map<int,int> cnt;
int mx=0;
for(auto i:a)
{
cnt[i]++;
mx=max(mx,cnt[i]);
}
return (mx<=4);
}
void subtask(int m, std::vector<int> a)
{
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
cur.pb(0);
for(int j=0;j<a.size();j++)
cur.pb(a[j]);
cur.pb(0);
for(int j=1;j<cur.size();j++)
child[cur[j-1]].push_back(cur[j]);
vector<int> x,y;
int s=0;
for(int i=0;i<=m;i++)
{
if(child[i].size()==1)
{
ans[i]=child[i][0];
}
else if(child[i].size()==2) // solve atmost 2
{
// We need
s++;
ans[i]=-s;
x.pb(child[i][0]);
y.pb(child[i][1]);
}
else if(child[i].size()==3)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(-s1);
y.pb(child[i][1]);
//s3
x.pb(child[i][0]);
y.pb(child[i][2]);
}
else if(child[i].size()==4)
{
int s1=s+1;
int s2=s+2;
int s3=s+3;
s+=3;
ans[i]=-s1;
// s1
x.pb(-s2);
y.pb(-s3);
//s2
x.pb(child[i][0]);
y.pb(child[i][2]);
//s3
x.pb(child[i][1]);
y.pb(child[i][3]);
}
}
// for(int i=0;i<=m;i++)
// {
// cout<<ans[i]<<' ';
// }
// cout<<endl;
// for(int i=0;i<s;i++)
// {
// cout<<x[i]<<' '<<y[i]<<endl;
// }
answer(ans,x,y);
}
void create_circuit(int m, std::vector<int> a)
{
if(check(m,a))
{
subtask(m,a);
return;
}
XP.clear();
YP.clear();
label=0;
vector<int> ans(m+1);
vector<int> child[m+2];
vector<int> cur;
int szp=a.size();
int lg=log2(sz);
int pw=(1<<lg);
if(pw==szp)
{
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;
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);
int cpp=0;
for(int j=zxp;j<pw;j++)
fl[cpp]=-NM,cpp++;
for(int j=0;j<zxp;j++)
fl[cpp]=child[i][j],cpp++;
father_of_all=-label-1;
childx.clear();
childy.clear();
order_.clear();
npp.clear();
ll og=label;
father_of_all=-label-1;
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);
generate_order(root);
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];
}
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;
}
}
answer(ans,XP,YP);
}
else
{
cur.pb(0);
for(int j=0;j<a.size();j++)
cur.pb(a[j]);
cur.pb(0);
for(int j=1;j<cur.size();j++)
child[cur[j-1]].push_back(cur[j]);
for(int i=0;i<=m;i++)
{
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);
int cpp=0;
for(int j=zxp;j<pw;j++)
fl[cpp]=-NM,cpp++;
for(int j=0;j<zxp;j++)
fl[cpp]=child[i][j],cpp++;
father_of_all=-label-1;
childx.clear();
childy.clear();
order_.clear();
npp.clear();
ll og=label;
father_of_all=-label-1;
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);
generate_order(root);
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];
}
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;
}
}
answer(ans,XP,YP);
}
}
Compilation message
doll.cpp: In function 'void generate_order(int)':
doll.cpp:111:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | if(my_order.size()==req_sz)return;
| ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void subtask(int, std::vector<int>)':
doll.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int j=0;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int j=1;j<cur.size();j++)
| ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:219:14: error: 'sz' was not declared in this scope; did you mean 'szp'?
219 | int lg=log2(sz);
| ^~
| szp
doll.cpp:225:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
225 | for(int j=1;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:241:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
241 | while(child[i].size()>pw)
| ~~~~~~~~~~~~~~~^~~
doll.cpp:267:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
267 | for(int k=0;k<child[i].size();k++)
| ~^~~~~~~~~~~~~~~~
doll.cpp:273:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
273 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:278:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
278 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:228:7: warning: unused variable 'lps' [-Wunused-variable]
228 | int lps=0;
| ^~~
doll.cpp:292:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
292 | for(int j=0;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:295:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
295 | for(int j=1;j<cur.size();j++)
| ~^~~~~~~~~~~
doll.cpp:307:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
307 | while(child[i].size()>pw)
| ~~~~~~~~~~~~~~~^~~
doll.cpp:333:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
333 | for(int k=0;k<child[i].size();k++)
| ~^~~~~~~~~~~~~~~~
doll.cpp:339:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
339 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:344:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
344 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
