Submission #1245687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245687		Gabriel	Mechanical Doll (IOI18_doll)	C++17	53 / 100	100 ms	15720 KiB

doll

#include "doll.h"
#include "bits/stdc++.h"
using namespace std;
void create_circuit(int m, vector<int> a){
  int n = a.size();
  map<int, int> _Facil_simo_verdad_;
  bool F_cil = 1;
  for(int i = 0; i < n and F_cil; i++){
    _Facil_simo_verdad_[a[i]]++;
    if(_Facil_simo_verdad_[a[i]] > 2) F_cil = 0;
  }
  if(F_cil){
    vector< vector<int> > Grafo(m + 1);
    vector<int> c(m + 1);
    for(int i = 1; i < n; i++){
      Grafo[a[i - 1]].push_back(a[i]);
    }
    Grafo[a.back()].push_back(0);
    c[0] = a[0];
    vector<int> x, y;
    int Interruptor = -1;
    for(int i = 1; i < m + 1; i++){
      if(Grafo[i].empty()) c[i] = 0;
      if(Grafo[i].size() == 1){
        x.push_back(Interruptor);
        y.push_back(Grafo[i][0]);
        c[i] = Interruptor;
        Interruptor--;
      }
      if(Grafo[i].size() == 2){
        x.push_back(Grafo[i][0]);
        y.push_back(Grafo[i][1]);
        c[i] = Interruptor;
        Interruptor--;
      }
    }
    answer(c, x, y);
    return;
  }
  vector<int> c(m + 1);
  c[0] = a[0];
  if(a.size() == 1){
    for(int i = 1; i < m + 1; i++) c[i] = 0;
    answer(c, vector<int>(0, 0), vector<int>(0, 0));
    return;
  }
  a.erase(a.begin());
  vector<int> Posiciones = {0, 1};
  for(int i = 1; i < m + 1; i++) c[i] = -1;
  int Necesitamos = 1, A_adir = 2, Capas = 1;
  while(Posiciones.size() < n){
    vector<int> Nuevo;
    for(int i = 0; i < Posiciones.size(); i++){
      Nuevo.push_back(Posiciones[i]);
      Nuevo.push_back(Posiciones[i] + Posiciones.size());
    }
    Posiciones = Nuevo;
    Necesitamos += A_adir;
    A_adir *= 2;
    Capas++;
  }
  vector<int> x(Necesitamos), y(Necesitamos);
  for(int i = 0; i < Necesitamos - A_adir / 2; i++){
    x[i] = (i + 1) * -2;
    y[i] = (i + 1) * -2 - 1;
  }
  int Estamos_aqu_ = 0;
  n--;
  for(int i = Necesitamos - A_adir / 2; i < Necesitamos; i++){
    if(Posiciones[Estamos_aqu_] < n) x[i] = a[Posiciones[Estamos_aqu_]];
    else x[i] = -1;
    Estamos_aqu_++;
    if(Posiciones[Estamos_aqu_] < n) y[i] = a[Posiciones[Estamos_aqu_]];
    else y[i] = -1;
    Estamos_aqu_++;
  }
  y.back() = 0;
  answer(c, x, y);
}

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