Submission #132694

#	Time	Username	Problem	Language	Result	Execution time	Memory
132694		dvdg6566	자동 인형 (IOI18_doll)	C++14	0 / 100	39 ms	6368 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 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;
  }
}

vi C;

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[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[cur] == 1){
          Y[-1-cur] = occ[x][t];
        }else{
          X[-1-cur] = occ[x][t];
        }
        states[cur] = 1-states[cur];
        break;
      }else{
        states[cur] = 1-states[cur];
        cur = nxt;
      }
      break;
    }
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  C.resize(M+1,-1);
  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)continue;
    if (SZ(occ[i]) == 1){
      C[i] = occ[i][0];
      continue;
    }
    int N = SZ(occ[i]);
    int t = MSB(N-1);
    int l = (1<<t);
    C[i] = c--;
    fill(N,l,-1);
  }
  // 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]) > 1)simulate(i);
  }
  // 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