Submission #464032

#	Time	Username	Problem	Language	Result	Execution time	Memory
464032		oscar1f	Mechanical Doll (IOI18_doll)	C++17	100 / 100	144 ms	20404 KiB

doll

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

const int DECA=(1<<18),INFINI=1000*1000*1000;
int nbDec,longChaine,date,decalage;
vector<int> chaine,direc,prem,deuz;
int arbreBin[2*DECA],tour[2*DECA][3];

void chute(int pos,int id) {
  if (pos<decalage) {
    tour[pos][2]=1-tour[pos][2];
    chute(tour[pos][1-tour[pos][2]],id);
  }
  else {
    arbreBin[pos]=chaine[id];
  }
}

void create_circuit(int M,vector<int> A) {
  nbDec=M;
  A.push_back(0);
  longChaine=A.size();
  chaine=A;
  decalage=1;
  while (decalage<longChaine) {
    decalage*=2;
  }
  for (int i=1;i<2*DECA;i++) {
    arbreBin[i]=INFINI;
    tour[i][0]=1;
    tour[i][1]=1;
  }
  for (int i=decalage-1;i>=decalage-longChaine;i--) {
    arbreBin[decalage+i]=1;
  }
  for (int i=0;i<=nbDec;i++) {
    direc.push_back(-1);
  }
  
  for (int i=decalage-1;i>0;i--) {
    if (arbreBin[2*i]!=INFINI) {
      tour[i][0]=2*i;
      arbreBin[i]=INFINI+1;
    }
    if (arbreBin[2*i+1]!=INFINI) {
      tour[i][1]=2*i+1;
      arbreBin[i]=INFINI+1;
    }
  }

  /*cout<<decalage<<endl;
  for (int i=1;i<decalage;i++) {
    cout<<tour[i][0]<<" "<<tour[i][1]<<endl;
  }*/
  
  for (int i=0;i<longChaine;i++) {
    chute(1,i);
  }  
  date=-1;

  for (int i=1;i<2*decalage;i++) {
    if (arbreBin[i]==INFINI+1) {
      arbreBin[i]=date;
      date--;
    }
    else if (arbreBin[i]==INFINI) {
      arbreBin[i]=-1;
    }
  }
  for (int i=1;i<decalage;i++) {
    if (arbreBin[i]<-1 or i==1) {
      prem.push_back(arbreBin[tour[i][0]]);
      deuz.push_back(arbreBin[tour[i][1]]);
    }
  }
  /*for (int i=0;i<direc.size();i++) {
    cout<<direc[i]<<" ";
  }
  cout<<endl;
  for (int i=0;i<prem.size();i++) {
    cout<<prem[i]<<" "<<deuz[i]<<endl;
  }*/
  answer(direc,prem,deuz);
}

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