Submission #132684

#	Time	Username	Problem	Language	Result	Execution time	Memory
132684		dvdg6566	Mechanical Doll (IOI18_doll)	C++14	0 / 100	48 ms	7672 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[100100];
int c=-1;
vi X,Y;

void fill(int sizes, int numfill, int exit, int rt){
  cout<<sizes<<' '<<numfill<<' '<<exit<<'\n';
  if (sizes == numfill){
    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);
    fill (sizes/2,numfill/2,0,rt);
    Y[t] = c--;
    if (exit)fill (sizes/2,numfill/2,1,rt);
    else fill(sizes/2,numfill/2,0,rt);
    return;
  }
  if (numfill == 2){
    if (sizes == 1){
      X.pb(rt);
      Y.pb(1-exit);
    }else{
      X.pb(1);
      Y.pb(1-exit);
    }
    return;
  }
  if (sizes*2 <= numfill){
    X.pb(rt);
    Y.pb(c--);
    fill (sizes, numfill/2, 0, rt);
    return;
  }else{
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    fill (sizes-numfill/2, numfill/2, 0, rt);
    Y[t] = c--;
    fill (numfill/2,numfill/2,exit,rt);
    return;
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  std::vector<int> C(M + 1,-1);
  if (M == 1){
    int t = MSB(N-1);
    int l = (1<<t);
    C[1] = c--; 
    C[0]=1;
    fill(N,l,1,-1);
    



  }else{
    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]);
      }
    }
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<'\n';
  answer(C,X,Y);
}

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