Submission #425503

#	Time	Username	Problem	Language	Result	Execution time	Memory
425503		dvdg6566	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	701 ms	15920 KiB

doll

    #include "doll.h"
    #include<bits/stdc++.h>
    using namespace std;
    typedef vector<int> vi;
    #define pb emplace_back
    #define SZ(x) (int)x.size()
     
    inline int MSB(unsigned int x){
      return 32-__builtin_clz(x);
    }
    #define INF 1e9
     
    vi occ[130100];
    int c=-1;
    vi X,Y;
     
    void fill(int sizes, int numfill, int rt){
      // cout<<sizes<<' '<<numfill<<' '<<exit<<'\n';
      if (sizes == numfill){
        if (sizes == 2){
          X.pb(1);Y.pb(1);
          return;
        }
        int t=SZ(X);
        X.pb(c--);
        Y.pb(0);
        fill (sizes/2,numfill/2,rt);
        Y[t] = c--;
        fill(sizes/2,numfill/2,rt);
        return;
      }
      if (numfill == 2){
        if (sizes == 1){
          X.pb(rt);
          Y.pb(1);
        }else{
          X.pb(1);
          Y.pb(1);
        }
        return;
      }
      if (sizes*2 <= numfill){
        X.pb(rt);
        Y.pb(c--);
        fill (sizes, numfill/2,rt);
        return;
      }else{
        int t=SZ(X);
        X.pb(c--);
        Y.pb(0);
        fill (sizes-numfill/2, numfill/2, rt);
        Y[t] = c--;
        fill (numfill/2,numfill/2,rt);
        return;
      }
    }
     
    void f2(int sizes, int numf2, int exit, int rt){
      // cout<<sizes<<' '<<numf2<<' '<<exit<<'\n';
      if (sizes == numf2){
        if (sizes == 2){
          if (exit){
            X.pb(1);
            Y.pb(0);
          }else{
            X.pb(1);
            Y.pb(1);
          }
          return;
        }
        int t=SZ(X);
        X.pb(c--);
        Y.pb(0);
        f2 (sizes/2,numf2/2,0,rt);
        Y[t] = c--;
        if (exit)f2 (sizes/2,numf2/2,1,rt);
        else f2(sizes/2,numf2/2,0,rt);
        return;
      }
      if (numf2 == 2){
        if (sizes == 1){
          X.pb(rt);
          Y.pb(1-exit);
        }else{
          X.pb(1);
          Y.pb(1-exit);
        }
        return;
      }
      if (sizes*2 <= numf2){
        X.pb(rt);
        Y.pb(c--);
        f2 (sizes, numf2/2, 0, rt);
        return;
      }else{
        int t=SZ(X);
        X.pb(c--);
        Y.pb(0);
        f2 (sizes-numf2/2, numf2/2, 0, rt);
        Y[t] = c--;
        f2 (numf2/2,numf2/2,exit,rt);
        return;
      }
    }
     
    vi C;
    int states[270100];
     
    void simulate(int x){
      map<int,int> states;
      for (int t=0;t<SZ(occ[x]);++t){
        int cur=C[x];
        // cout<<"Simulate with dest "<<occ[x][t]<< " from "<<cur<<'\n';
        while (1){
          int nxt = X[-1-cur];
          if (states[-1-cur] == 1){
            nxt = Y[-1-cur];
          }
          // cout<<"At "<<cur<<" aka "<<-1-cur<<" next is "<<nxt<<'\n';
          if (nxt == 1){
            // cout<<"Change "<<-1-cur<<" when the state is "<<cur<<'\n';
            if (states[-1-cur] == 1){
              Y[-1-cur] = occ[x][t];
            }else{
              X[-1-cur] = occ[x][t];
            }
            states[-1-cur] = 1-states[-1-cur];
            break;
          }else{
            states[-1-cur] = 1-states[-1-cur];
            cur = nxt;
          }
        }
      }
    }
     
    void create_circuit(int M, std::vector<int> A) {
      int N = A.size();
      C.resize(M+1,-1);
      if (M == 1){
        int t = MSB(N-1);
        int l = (1<<t);
        C[1] = c--; 
        C[0]=1;
        f2(N,l,1,-1);
        answer(C,X,Y);
        return;
      }
      occ[0].pb(A[0]);
      for (int i=0;i<N-1;++i){
        occ[A[i]].pb(A[i+1]);
      }
      occ[A[N-1]].pb(0);
      for (int i=0;i<=M;++i){
        if (SZ(occ[i]) == 0){
          C[i]=0;
        }else if(SZ(occ[i]) == 1){
          C[i]=occ[i][0];
        }else if (SZ(occ[i]) == 2){
          C[i] = c;
          --c;
          X.pb(occ[i][0]);
          Y.pb(occ[i][1]);
        }else if (SZ(occ[i]) == 3){
          int a = c;
          C[i] = a;
          c -= 3;
          X.pb(a-1);
          Y.pb(a-2);
          X.pb(occ[i][0]);
          Y.pb(a);
          X.pb(occ[i][1]);
          Y.pb(occ[i][2]);
        }else if (SZ(occ[i]) == 4){
          int a = c;
          C[i] = a;
          c -= 3;
          X.pb(a-1);
          Y.pb(a-2);
          X.pb(occ[i][0]);
          Y.pb(occ[i][2]);
          X.pb(occ[i][1]);
          Y.pb(occ[i][3]);
        }else{
          int N = SZ(occ[i]);
          int t = MSB(N-1);
          int l = (1<<t);
          int cc=c;
          C[i] = c--;
          fill(N,l,cc);
        }
        // cout<<"Value "<<i<<" ends at "<<c<<'\n';
        // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
      }
      // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
      // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
      for (int i=0;i<=M;++i){
        if (SZ(occ[i]) > 4)simulate(i);
      }
      // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
      // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
      // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<'\n';
      answer(C,X,Y);
    }

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