#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++;
child[fk].clear();
state[fk]=0;
if(!use)
{
// all minus one is subtree
// cout<<"Range "<<l<<' '<<r<<endl;
// cout<<"Child: "<<father_of_all<<' '<<father_of_all<<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<<"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;
if(child[cur].size()==0)
{
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;
{
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]);
int lps=0;
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);
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);
generate_order(root);
// cout<<"My Order: ";
// for(auto i:my_order)
// cout<<i<<' ';
// cout<<endl;
// cout<<"Req order: ";
// for(auto j:child[i])
// {
// cout<<j<<' ';
// }
// cout<<endl;
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;
}
}
cout<<"ans\n";
for(int i=0;i<=m;i++)
{
cout<<ans[i]<<' ';
}
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<<XP[i]<<' '<<YP[i]<<endl;
}
answer(ans,XP,YP);
}
}
Compilation message
doll.cpp: In function 'void generate_order(int)':
doll.cpp:124:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
124 | if(my_order.size()==req_sz)return;
| ~~~~~~~~~~~~~~~^~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:144:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for(int j=0;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:147:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int j=1;j<cur.size();j++)
| ~^~~~~~~~~~~
doll.cpp:160:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
160 | while(child[i].size()>pw)
| ~~~~~~~~~~~~~~~^~~
doll.cpp:203:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for(int k=0;k<child[i].size();k++)
| ~^~~~~~~~~~~~~~~~
doll.cpp:209:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
209 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
214 | for(int i=0;i<order_.size();i++)
| ~^~~~~~~~~~~~~~
doll.cpp:149:7: warning: unused variable 'lps' [-Wunused-variable]
149 | int lps=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26972 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26972 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
26972 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
54548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
54616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
54616 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
