Submission #198363

#	Time	Username	Problem	Language	Result	Execution time	Memory
198363		DavidDamian	Mechanical Doll (IOI18_doll)	C++11	85.55 / 100	204 ms	42044 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
struct parent
{
    int p,edge;
};
vector<int> Exits[1000006];
vector<int> X;
vector<int> Y;
map<int,parent> memo;
int NEXT_FREE_INDEX=1;
void createTree(int root,int i,int lv,int limit,int sum,int unused)
{
    if(lv==limit-1){ //Last level of switches
        if(unused==1)
            X.push_back(-root);
        else{
            X.push_back(sum);
            parent x={i,0};
            memo[sum]=x;
        }
        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
            X.push_back(-root);
            Y.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            createTree(root,NEXT_FREE_INDEX-1,lv+1,limit,sum+(1<<lv),unused-child_size);
        }
        else{
            X.push_back(-NEXT_FREE_INDEX);
            NEXT_FREE_INDEX++;
            Y.push_back(0);
            createTree(root,NEXT_FREE_INDEX-1,lv+1,limit,sum,unused);
            Y[i-1]=-NEXT_FREE_INDEX;
            NEXT_FREE_INDEX++;
            createTree(root,NEXT_FREE_INDEX-1,lv+1,limit,sum+(1<<lv),0);
        }
    }
}
int logn[200005];
void create_circuit(int m, vector<int> A) {
  for(int i=2;i<=200000;i++){
    logn[i]=logn[(i+1)/2]+1;
  }
  int n=A.size();
  vector<int> C(m+1);
  C[0]=A[0];
  for(int i=0;i<n-1;i++){
    Exits[ A[i] ].push_back(A[i+1]);
  }
  Exits[ A[n-1] ].push_back(0);
  for(int i=1;i<=m;i++){
    if(Exits[i].size()==0) C[i]=0;
    else if(Exits[i].size()==1) C[i]=Exits[i][0];
    else{ //Create a tree
        C[i]=-NEXT_FREE_INDEX;
        NEXT_FREE_INDEX++;
        int LOG=logn[ Exits[i].size() ];
        createTree(-C[i],-C[i],0,LOG,0,(1<<LOG)-Exits[i].size());
        int j=0;
        for(auto x: memo){
            int p=x.second.p;
            int edge=x.second.edge;
            if(edge==0) X[p-1]=Exits[i][j];
            else Y[p-1]=Exits[i][j];
            j++;
        }
        memo.clear();
    }
  }
  /*for(int i=0;i<NEXT_FREE_INDEX;i++){
    cout<<X[i]<<" "<<Y[i]<<endl;
  }*/
  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: 41.5530038336 / 56