Submission #1245736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245736		candi_ositos	Mechanical Doll (IOI18_doll)	C++20	53 / 100	71 ms	16580 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector <int> C, X, Y, A;
void create_switch(vector <int> xd, int ind){
  int nsc=xd.size();
  if(nsc==0){
    return;
  }
  if(nsc==1){
    C[ind]=xd[0];
    return;
  }
  vector <int> aguss;
  int papa=-1;
  int i=1;
  while(i<2*nsc){
    i*=2;
    ++papa;
  }
  i/=2;
  int sp=X.size();
  aguss.assign(i-nsc, -sp-1);
  for(int j=i-nsc; j<i; ++j){
    aguss.push_back(xd[j-i+nsc]);
  }
  xd=aguss;
  nsc=i;
  X.resize(X.size()+nsc-1);
  Y.resize(Y.size()+nsc-1);
  i=i/2-1;
  C[ind]=-sp-1;
  for(int j=0; j<i; ++j){
    X[sp+j]=-sp-2*j-2;
    Y[sp+j]=-sp-2*j-3;
  }
  for(int j=0; j<nsc; ++j){
    int m=-sp;
    int aux=j;
    for(int potato=1; potato<papa; ++potato){
      if(aux%2){
        m=Y[-m]+1;
      }
      else{
        m=X[-m]+1;
      }
      aux/=2;
    }
    if(aux%2){
      Y[-m]=xd[j];
    }
    else{
      X[-m]=xd[j];
    }
  }
  sp+=nsc;
  return;
}
void create_circuit(int xd, vector <int> dx){
  M=xd+1;
  dx.push_back(0);
  N=dx.size();
  A=dx;
  C.assign(M, 0);
  vector <vector <int> > conn;
  conn.resize(M);
  conn[0].push_back(A[0]);
  for(int i=1; i<N; ++i){
    conn[A[i-1]].push_back(A[i]);
  }
  for(int i=0; i<M; ++i){
    create_switch(conn[i], i);
  }
  answer(C, X, Y);
  return;
}

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