Submission #1210284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210284		loiiii12358	Mechanical Doll (IOI18_doll)	C++20	100 / 100	77 ms	10788 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int pt=0;
vector<int> a,X={0},Y={0};
vector<bool> states;

void solve(int id,int d,int len){
  // cout << id << ' ' << d << ' ' << len << '\n';
  int cnt=len-(1<<d);
  if(cnt<=0){
    X[id]=-1;
  }else if(d==0){
    X[id]=0;
  }else{
    int tmp=X.size();
    X[id]=-tmp-1;
    X.push_back(0);Y.push_back(0);
    solve(tmp,d-1,cnt);
  }
  if(d==0){
    Y[id]=0;
  }else{
    int tmp=X.size();
    Y[id]=-tmp-1;
    X.push_back(0);Y.push_back(0);
    solve(tmp,d-1,min(1<<d,len));
  }
}

void run(int now){
  // cout << now << endl;
  if(pt==a.size()){
    return;
  }
  if(now==0){
    return;
  }else if(states[-now-1]){
    states[-now-1]=!states[-now-1];
    if(Y[-now-1]==0){
      Y[-now-1]=a[pt++];
      run(-1);
    }else{
      run(Y[-now-1]);
    }
  }else{
    states[-now-1]=!states[-now-1];
    if(X[-now-1]==0){
      X[-now-1]=a[pt++];
      run(-1);
    }else{
      run(X[-now-1]);
    }
  }
}

void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  a=A;
  for(int i=1;i<20;i++){
    if((1<<i)>=A.size()){
      solve(0,i-1,A.size());
      break;
    }
  }
  states.resize(X.size(),false);
  run(-1);
  vector<int> C(M+1,-1);
  answer(C, X, Y);
}

//9 -> 16
//

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