Submission #1014320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014320		Dzadzo	Mechanical Doll (IOI18_doll)	C++17	0 / 100	4 ms	8284 KiB

doll

#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);
}
*/

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56