제출 #464018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464018		oscar1f	자동 인형 (IOI18_doll)	C++17	37 / 100	142 ms	12936 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];

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

void create_circuit(int M,vector<int> A) {
  nbDec=M;
  longChaine=A.size();
  chaine=A;
  decalage=1;
  while (decalage<longChaine+1) {
    decalage*=2;
  }
  for (int i=1;i<2*DECA;i++) {
    arbreBin[i]=INFINI;
  }
  for (int i=0;i<=nbDec;i++) {
    direc.push_back(-1);
  }
  for (int i=0;i<longChaine;i++) {
    chute(1,i);
  }
  arbreBin[2*decalage-1]=0;
  for (int i=decalage-1;i>0;i--) {
    if (arbreBin[2*i]!=INFINI or arbreBin[2*i+1]!=INFINI) {
      arbreBin[i]=0;
    } 
  }
  date=-1;
  for (int i=1;i<decalage;i++) {
    if (arbreBin[i]==0) {
      arbreBin[i]=date;
      date--;
    }
  }
  for (int i=1;i<decalage;i++) {
    if (arbreBin[i]<0) {
      if (arbreBin[2*i]!=INFINI) {
        prem.push_back(arbreBin[2*i]);
      }
      else {
        prem.push_back(-1);
      }
      if (arbreBin[2*i+1]!=INFINI) {
        deuz.push_back(arbreBin[2*i+1]);
      }
      else {
        deuz.push_back(-1);
      }
    }
  }
  /*for (int i=0;i<direc.size();i++) {
    cout<<direc[0]<<" ";
  }
  cout<<endl;
  for (int i=0;i<prem.size();i++) {
    cout<<prem[i]<<" "<<deuz[i]<<endl;
  }*/
  answer(direc,prem,deuz);
}

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