#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=4e5+10;
ll cp[NM],final[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;
}
void label_it(vll p)
{
if(p.size()==1)return;
vll np;
for(int i=0;i<p.size();i+=2)
{
label++;
np.pb(-label);
if(p[i]==-NM)// problem
p[i]=father_of_all;
if(p[i+1]==-NM)
p[i+1]=father_of_all;
XP.pb(p[i]);
YP.pb(p[i+1]);
}
label_it(np);
}
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;
ll cnt_minus=pw-(ll)child[i].size();
for(int j=0,k=0;j<pw;)
{
if(cnt_minus>0)
{
cp[j]=-NM;
cp[j+1]=child[i][k];
k++;
j+=2;
cnt_minus--;
}
else
{
cp[j]=child[i][k];
k++;
j++;
}
}
// for(int j=0;j<child[i].size();j++)
// cp[j]=child[i][j];
// for(int j=child[i].size();j<pw;j++)
// cp[j]=-NM;
vll order=fast_order(pw);
vll fl(pw);
for(int j=0;j<pw;j++)
{
order[j]--;
fl[order[j]]=cp[j];
final[order[j]]=cp[j];
}
// cout<<"final: ";
// for(int j=0;j<pw;j++)
// cout<<final[j]<<' ';
// cout<<endl;
// what switches?
father_of_all=-label-pw;
// pw then
label_it(fl);
// cout<<"AT "<<i<<' '<<label<<endl;;
ans[i]=-label;
}
/*
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]);
}
*/
}
// cout<<"ans\n";
// for(int i=0;i<=m;i++)
// {
// cout<<ans[i]<<' ';
// }
// cout<<endl;
// cout<<"xy\n";
// for(int i=0;i<label;i++)
// {
// cout<<XP[i]<<' '<<YP[i]<<endl;
// }
answer(ans,XP,YP);
}
Compilation message
doll.cpp: In function 'void label_it(std::vector<int>)':
doll.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<p.size();i+=2)
| ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int j=0;j<a.size();j++)
| ~^~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int j=1;j<cur.size();j++)
| ~^~~~~~~~~~~
doll.cpp:71:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
71 | while(child[i].size()>pw)
| ~~~~~~~~~~~~~~~^~~
doll.cpp:60:6: warning: unused variable 'lps' [-Wunused-variable]
60 | int lps=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
15 ms |
5584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
21 ms |
8288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
15 ms |
5584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
21 ms |
8288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
34 ms |
7888 KB |
Output is correct |
| 9 |
Correct |
35 ms |
9168 KB |
Output is correct |
| 10 |
Correct |
62 ms |
12232 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
15 ms |
5584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
21 ms |
8288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
34 ms |
7888 KB |
Output is correct |
| 9 |
Correct |
35 ms |
9168 KB |
Output is correct |
| 10 |
Correct |
62 ms |
12232 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
64 ms |
11956 KB |
wrong serial number |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
