#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF INT_MAX
#define MOD 1000000007
#define MAXN 500000
using namespace std;
vi f(MAXN+1);
vector < pair < int , pii > > go(int val) {
if (val==2) {
f[1]=-1;
return { { -1 ,{ 1 ,2 } } };
}
vector <pair <int,pii>>arr=go(val/2);
vi newf(MAXN+1);
for (int i=1;i<=val/4;i++) {
newf[i]=f[i]*2;
newf[i+val/4]=f[i]*2-1;
}
f=newf;
vector < pair <int,pii> > res ={ {-1 , { -2 , -3 } } };
for (auto x:arr) {
int sw=x.F;
int X=x.S.F;
int Y=x.S.S;
if (X<0 && Y<0) {
res.pb({sw*2,{X*2,Y*2}});
res.pb({sw*2-1,{X*2-1,Y*2-1}});
}else{
res.pb({sw*2,{X*2-1,Y*2-1}});
res.pb({sw*2-1,{X*2,Y*2}});
}
}
return res;
}
void dfs(int v,int p,int dir,vi &X,vi &Y) {
if (X[-v-1] == -1 && Y[-v-1] == -1) {
if (dir==0)X[-p-1]=-1;else Y[-p-1] = -1 ;
}
if (X[-v-1] != -1 && X[-v-1] < 0) dfs(X[-v-1],v,0,X,Y);
if (Y[-v-1] != -1 && Y[-v-1] < 0) dfs(Y[-v-1],v,1,X,Y);
}
vi g(MAXN+1,-1);
vi z(MAXN+1);
int CNT=0;
void label(int v,vi &X,vi &Y) {
g[-v-1]=--CNT;
// cout<<CNT<<'\n';
if (X[-v-1] != -1 && X[-v-1] < 0) label(X[-v-1],X,Y);
if (Y[-v-1] != -1 && Y[-v-1] < 0) label(Y[-v-1],X,Y);
}
vector <pair <int , pii >> ans;
void solve(int v,vi &X,vi &Y) {
int k1,k2;
if (X[-v-1]<0)k1=g[-X[-v-1]-1];else k1=z[X[-v-1]];
if (Y[-v-1]<0)k2=g[-Y[-v-1]-1];else k2=z[Y[-v-1]];
ans.pb({g[-v-1],{k1,k2}});
if (X[-v-1] != -1 && X[-v-1] < 0) solve(X[-v-1],X,Y);
if (Y[-v-1] != -1 && Y[-v-1] < 0) solve(Y[-v-1],X,Y);
}
void create_circuit(int m, vi a) {
a.pb(0);
int n=a.size();
int k=1;
while (k<2*n)k*=2;
k/=2;
vi C(m+1);
for (int i=0;i<=m;i++)C[i]=-1;
vector <pair <int,pii>>arr=go(k);
vi X(arr.size()),Y(arr.size());
for (auto t:arr) {
X[-t.F-1]=t.S.F;
Y[-t.F-1]=t.S.S;
}
set <int> s;
for (int i=1;i<=k;i++)s.insert(i);
int cnt=k-n;
int ind=1;
while (cnt>0) {
if (cnt==1) {
s.erase(X[-f[ind]-1]);
X[-f[ind]-1]=-1;
break;
}
s.erase(X[-f[ind]-1]);
s.erase(Y[-f[ind]-1]);
X[-f[ind]-1]=-1;
Y[-f[ind]-1]=-1;
cnt-=2;
ind++;
}
dfs(-1,0,0,X,Y);
label(-1,X,Y);
int cur=0;
for (int x:s)z[x]=a[cur++];
solve(-1,X,Y);
/*cout<<arr.size()<<"\n";
for (int i=0;i<arr.size();i++)cout<<-i-1<<" "<<X[i]<<" "<<Y[i]<<'\n';
cout<<"---\n";*/
// cout<<CNT<<'\n';
vi ansX(-CNT),ansY(-CNT);
for (auto x:ans) {
ansX[-x.F-1] = x.S.F;
ansY[-x.F-1] = x.S.S;
}
answer(C,X,Y);
}
/*
signed main() {
int m;
cin>>m;
int n;
cin>>n;
vi a(n);
for (int i=1;i<=n;i++)cin>>a[i-1];
create_circuit(m,a);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8280 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8280 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8280 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8284 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8120 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8120 KB |
wrong serial number |
| 2 |
Halted |
0 ms |
0 KB |
- |
