Submission #812133

#	Time	Username	Problem	Language	Result	Execution time	Memory
812133		thimote75	Mechanical Doll (IOI18_doll)	C++14	70.67 / 100	85 ms	12528 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

using di = pair<int, int>;
using vd = vector<di>;

struct SegTree {
  idata treeIds;
  int rsize = 0;

  int start, height, size;

  void generate (int node, int limit) {
    if (node == 0) return ;

    generate(node >> 1, (limit + 1) >> 1);
    if (node == start) return ;
    for (int u = node; u < node + limit; u ++)
      treeIds[u] = - ((rsize ++) + 1);
  }
  int getId (int node) {
    int count = 0;
    int diam  = height - 1;
    while (node != 1) {
      if (node & 1) count += 1 << diam;

      diam --;
      node >>= 1;
    }

    return count;
  }

  idata X, Y;
  SegTree (idata A) {
    size   = A.size();
    height = ceil(log2(size + 1));
    start  = 1 << height;

    treeIds.resize(start << 1, - 1e9);

    generate(start, size);

    vd g_pos;
    for (int i = 0; i < size; i ++)
      g_pos.push_back({ getId( i + start ), i + start });
    
    sort(g_pos.begin(), g_pos.end());

    for (int i = 0; i < size; i ++)
      treeIds[g_pos [i].second] = A[i];
    
    X.resize(rsize); Y.resize(rsize);
    
    for (int i = 1; i < start; i ++) {
      if (treeIds[i] >= 0 || treeIds[i] == - 1e9) continue ;
      int xid = - (1 + treeIds[i]);

      int n0 = 2 * i;     int vn0 = treeIds[n0] == - 1e9 ? -1 : treeIds[n0];
      int n1 = 2 * i + 1; int vn1 = treeIds[n1] == - 1e9 ? -1 : treeIds[n1];
      X[xid] = vn0;
      Y[xid] = vn1;
    }
  }
};

void create_circuit(int M, vector<int> A) {
  idata C( M + 1, - 1 ); // - 1 is the decision tree root
  
  SegTree tree(A);
  
  idata X = tree.X;
  idata Y = tree.Y;

  int h = 1;
  int p = 0;
  while (h < tree.start) {
    if (tree.treeIds[h * 2 + 1] == - 1e9) {
      Y[p] = h * 2 + 1 >= tree.start ? 0 : - ((tree.rsize ++) + 1);

      if (Y[p] != 0) {
        X.push_back(-1);
        Y.push_back(-1);
      }
    }

    h = (h * 2) + 1;
    p = - (Y[p] + 1);
  }

  answer(C, X, Y);
}

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