Submission #198390

#	Time	Username	Problem	Language	Result	Execution time	Memory
198390		DavidDamian	Mechanical Doll (IOI18_doll)	C++11	100 / 100	233 ms	18492 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
///Binary Tree
///Create a tree of switches that produces a sequence of nodes
#define debug(x) cerr<<#x<<" = "<<x<<endl
struct parent
{
    int p;
    short edge;
};
vector<int> X;
vector<int> Y;
map<int,parent> memo;
int NEXT_FREE_INDEX=1;
int limit;
void createTree(int i,int lv,int sum,int unused) ///Creates a tree of switches to branch exits
{
    if(lv==limit-1){ //Last level of switches, so we direct the switches to the number of the sum
        if(unused==1) //We have to kill that edge
            X.push_back(-1);
        else{
            X.push_back(sum);
            parent x={i,0};
            memo[sum]=x; //We store where it is that number in the tree
        }
        sum+=(1<<lv);
        parent x={i,1};
        Y.push_back(sum);
        memo[sum]=x;
    }
    else{
        int child_size=(1<<(limit-lv-1));
        if(unused>=child_size){ //Drop left child because it not useful
            X.push_back(-1);
            Y.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),unused-child_size); //And just create right child
        }
        else{ //Create both children
            X.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            Y.push_back(0);
            createTree(NEXT_FREE_INDEX-1,lv+1,sum,unused);
            Y[i-1]=-NEXT_FREE_INDEX;
            NEXT_FREE_INDEX++;
            createTree(NEXT_FREE_INDEX-1,lv+1,sum+(1<<lv),0);
        }
    }
}
void create_circuit(int m, vector<int> A) {

  A.push_back(0);
  int n=A.size();
  vector<int> C(m+1);
  for(int i=0;i<=m;i++){ //We direct all the triggers to a single root
    C[i]=-1;
  }
  int LOG=0;
  while((1<<LOG)<n){
    LOG++;
  }
  NEXT_FREE_INDEX++;
  limit=LOG;
  createTree(1,0,0,(1<<LOG)-n);
  int j=0;
  map<int,parent>::iterator it;
    for(it=memo.begin();it!=memo.end();it++){
        pair<int,parent> x=(*it);
        int p=x.second.p;
        int edge=x.second.edge;
        if(edge==0) X[p-1]=A[j]; //Attach the correct node to exit 0 of the switch p-1
        else Y[p-1]=A[j]; //Attach the correct node to exit 1 of the switch p-1
        j++;
    }
    memo.clear();
  answer(C, X, Y);
}

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