Submission #1210271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210271		loiiii12358	Mechanical Doll (IOI18_doll)	C++20	28 / 100	63 ms	9980 KiB

doll

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

vector<int> X={0},Y={0};

void solve(int id,int d,vector<int> a){
  vector<int> l,r;
  int cnt=int(a.size())-(1<<d),pt=0;
  if(cnt<0){
    r=a;
  }else{
    pt=int(a.size())-2*cnt;
    for(int i=0;i<pt;i++){
      r.push_back(a[i]);
    }
    for(int i=0;i<2*cnt;i++){
      if(i%2==0){
        l.push_back(a[pt++]);
      }else{
        r.push_back(a[pt++]);
      }
    }
  }
  if(l.size()==0){
    X[id]=-1;
  }else if(d==0){
    X[id]=l[0];
  }else{
    int tmp=X.size();
    X[id]=-tmp-1;
    X.push_back(0);Y.push_back(0);
    solve(tmp,d-1,l);
  }
  if(d==0){
    Y[id]=r[0];
  }else{
    int tmp=X.size();
    Y[id]=-tmp-1;
    X.push_back(0);Y.push_back(0);
    solve(tmp,d-1,r);
  }
}

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

//9 -> 16
//

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