Submission #198145

#	Time	Username	Problem	Language	Result	Execution time	Memory
198145		DavidDamian	Mechanical Doll (IOI18_doll)	C++11	12 / 100	1070 ms	26576 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[4000006];
int Y[4000006];
int moved[4000006];
int parent[100005];
int removed[100005];
void connectLeaves(int n,int trigger)
{
    int leaf=0;
    for(int i=0;i<n;i++){
        if(removed[i]) continue;
        int id=parent[i];
        if(X[id]==i && !moved[id]) {
            X[id]=destino[trigger][leaf];
            moved[id]=1;
        }
        else Y[id]=destino[trigger][leaf];
        leaf++;
    }
}
void explore_PhantomTree(int limit,int lv,int sum)
{
    if(lv==limit-1){
        removed[sum]=1;
        sum+=(1<<lv);
        removed[sum]=1;
    }
    else{
        explore_PhantomTree(limit,lv+1,sum);
        explore_PhantomTree(limit,lv+1,sum+(1<<lv));
    }
}
int k;
int NEXT_FREE_INDEX=0;
void createTree(int i,int limit,int lv,int sum,int notDesired)
{
    //debug(i);
    //debug(lv);
    if(lv==limit-1){
        if(notDesired==0){
            X[i-1]=sum;
            parent[sum]=i-1;
        }
        else{
            X[i-1]=-k;
            removed[sum]=1;
        }
        sum+=(1<<lv);
        Y[i-1]=sum;
        parent[sum]=i-1;
        return;
    }
    int treeSize=(1<<(limit-lv-1));
    //debug(treeSize);
    //debug(notDesired);
    if(notDesired>=treeSize){ //Eliminate left child, all unused exits
        explore_PhantomTree(limit,lv+1,sum);
        X[i-1]=-k; //Kill out that exit (connect it to the root)
        Y[i-1]=-(++NEXT_FREE_INDEX);
        createTree(-Y[i-1],limit,lv+1,sum+(1<<lv),notDesired-treeSize);
    }
    else{
        X[i-1]=-(++NEXT_FREE_INDEX);
        Y[i-1]=-(++NEXT_FREE_INDEX);
        createTree(-X[i-1],limit,lv+1,sum,notDesired);
        createTree(-Y[i-1],limit,lv+1,sum+(1<<lv),0);
    }
}
int log_n[400005];
void create_circuit(int m, vector<int> A) {
  int n=A.size();
  log_n[2]=1;
  for(int i=3;i<=400000;i++){
    log_n[i]=log_n[(i+1)/2]+1;
  }
  vector<int> C(m + 1);
  C[0]=A[0];
  for(int i=0;i<n-1;i++){
    destino[ A[i] ].push_back(A[i+1]);
  }
  destino[ A[n-1] ].push_back(0);
  for(int i=1;i<=m;i++){
    if(destino[i].size()==0) C[i]=0;
    else if(destino[i].size()==1) C[i]=destino[i][0];
    else{ //Create a tree of switches
        memset(parent,0,sizeof(parent));
        memset(removed,0,sizeof(removed));
        memset(moved,0,sizeof(moved));
        int limit=log_n[ destino[i].size() ];
        C[i]=-(++NEXT_FREE_INDEX);
        k=-C[i];
        int notDesired=(1<<limit)-destino[i].size();
        createTree(-C[i],limit,0,0,notDesired);
        connectLeaves((1<<limit),i);
    }
  }
  vector<int> x,y;
  for(int i=0;i<NEXT_FREE_INDEX;i++){
    //debug(i);
    //debug(X[i]);
    //debug(Y[i]);
    x.push_back(X[i]);
    y.push_back(Y[i]);
  }
  answer(C, x, y);
}

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