Submission #601448

#	Time	Username	Problem	Language	Result	Execution time	Memory
601448		APROHACK	Mechanical Doll (IOI18_doll)	C++14	53 / 100	248 ms	45368 KiB

doll

#include "doll.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define ll long long
#define ff first 
#define ss second
#define pb push_back
using namespace std;

const ll NMAX = 200002; // el tamaño del camino
const ll MMAX = 100002; // el numero de triggers

vector<int>C, X, Y;
vector<int>adj[MMAX];
ll n, m, curr = -1;
ll pot2[40];
struct subarbol
{
  subarbol *L, *R;
  int deg, nodel=0, noder=0, indxRoot, thisIndex, usos=0, totaldeusos;
  bool first;
  subarbol(int dg, int indxR, int nodoanterior){
    thisIndex = curr--;
    totaldeusos=adj[nodoanterior].size();
    //cout<<"created at "<<indxR << " " << dg<<endl;
    deg=dg;
    first = true;
    indxRoot=indxR;
    if(dg>1){
      L = new subarbol(dg-1, indxR, nodoanterior);
      R = new subarbol(dg-1, indxR, nodoanterior);
      X[-thisIndex]=L->thisIndex;
      Y[-thisIndex]=R->thisIndex;
    }
  }

  bool insert(int value, bool firsted, bool ojo){
    usos++;
    if(usos >= totaldeusos)ojo=true;
    //cout<<thisIndex<<" "<<deg<< " " << first << " " << firsted << "  " << value << endl;
    if(deg>1){
      if(first){
        first=!first;
        return L->insert(value, true, ojo);
      }else{
        first=!first;
        return R->insert(value, firsted, ojo);
        
      }
    }else{
      if(first)firsted=true;
      if(!ojo){
        if(first)nodel = value;
        else {
          noder = value;
        }
        first=!first;
        X[-thisIndex]=nodel;
        Y[-thisIndex]=noder;
        return true;
      }else{
        if(!firsted){
          //cout<<"last at" << thisIndex<<endl;
          noder = value;
          first=!first;
          X[-thisIndex]=nodel;
          Y[-thisIndex]=noder;
          return true;
        }else{
          if(first)nodel = indxRoot;
          else noder = indxRoot;
          //cout<<"relleno en "<< thisIndex<<endl;
          first=!first;

          X[-thisIndex]=nodel;
          Y[-thisIndex]=noder;

          return false;

        }
      }
      //cout<<indxRoot << " " <<nodel << " " << noder << endl;
      
    }
    
  }


};

vector<int>recorrido;


vector<subarbol *>jungla;
bool created[MMAX];



void put(int dd, int ht){
  if(!created[dd]){
    C[dd]=ht;
  }else{
      while(!jungla[dd]->insert(ht, false, false)){
      }
    //llenar el arbol de dd con ht;
  }
}

void crearArbol(int nod){
  ll pot = adj[nod].size(), ans = 0;
  while(pot>1){
    if(pot%2==1)pot++;
    pot/=2;
    ans++;
  }
  //cout<<"creando para " << nod<<endl;
  C[nod]=curr;
  jungla[nod] = new subarbol(ans, curr, nod);
  created[nod]=true;
}






void create_circuit(int M, std::vector<int> A) {
  A.push_back(0);
  n = A.size(), m=M;
  C.pb(0);
  for(int i = 1 ; i <= m ; i ++){
    subarbol *x;
    C.pb(i);
    jungla.pb(x);
  }
  ll templol= 0;
  for(int i = 1 ; i <= NMAX*4 ; i*=2){
    pot2[templol++]=i;
  }
  
  for(int i = 0 ; i < 400000 ; i++)X.pb(0), Y.pb(0);
  subarbol *x;
  
  jungla.pb(x);

  
  for(int i = 0 ; i < n-1 ; i++){
    adj[A[i]].pb(A[i+1]);
  }
  adj[0].pb(A[0]);

  int current = 0;
  for(int i = 0 ; i < n ; i++){
    //tengo que ir a A[i]
    //cout<<" A ";
    if(adj[current].size()<=1 || created[current]){
      put(current, A[i]);
    }else{
      crearArbol(current);
      put(current, A[i]);
    }
    current=A[i];
  }
  /*
  cout<<endl;
  for(int i = 0 ; i <= m ; i++){
    cout<<C[i]<<" ";
  }
  cout<<endl;
  for(int i = 0 ; i < -curr ; i ++){
    cout<<X[i] << " " << Y[i] << endl;
  }*/
  vector<int>ansX, ansY;
  for(int i = 1 ; i < -curr ; i++){
    ansX.pb(X[i]);
    ansY.pb(Y[i]);
  }
  answer(C, ansX, ansY);
}

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