Submission #198067

#	Time	Username	Problem	Language	Result	Execution time	Memory
198067		DavidDamian	Mechanical Doll (IOI18_doll)	C++11	53 / 100	148 ms	20116 KiB

doll

#include "doll.h"
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[4000006];
int Y[4000006];
int create_tree(int i,int limit,int lv,int sum,int n,int root,int trigger)
{
    int last=i;
    if(lv==limit-1){
        int threshold=(1<<limit)-n;
        if(sum<threshold)
            X[(i+root-1)-1]=-root;
        else
            X[(i+root-1)-1]=destino[trigger][sum-threshold];
        sum+=(1<<lv);
        //debug(sum);
        if(sum<threshold)
            Y[(i+root-1)-1]=-root;
        else
            Y[(i+root-1)-1]=destino[trigger][sum-threshold];
    }
    else{
        X[i+root-1-1]=-(2*i+root-1);
        last=max(last,create_tree(i*2,limit,lv+1,sum,n,root,trigger));
        Y[i+root-1-1]=-(2*i+root);
        last=max(last,create_tree(i*2+1,limit,lv+1,sum+(1<<lv),n,root,trigger));
    }
    return last;
}
int log_n[400005];
int k;
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{
        int limit=log_n[ destino[i].size() ];
        C[i]=-(k+1);
        k+=create_tree(1,limit,0,0,destino[i].size(),k+1,i);
        //debug(k);
    }
  }
  vector<int> x,y;
  for(int i=0;i<k;i++){
    x.push_back(X[i]);
    y.push_back(Y[i]);
  }
  answer(C, x, y);
}

• 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