Submission #812237

#	Time	Username	Problem	Language	Result	Execution time	Memory
812237		thimote75	Mechanical Doll (IOI18_doll)	C++14	100 / 100	93 ms	13252 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, int end) {
    if (node == 0) return ;

    generate(node >> 1, (limit + 1) >> 1, end >> 1);
    if (node == start) return ;

    for (int u = end - limit; u < end; 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));
    start  = 1 << height;

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

    generate(start, size, treeIds.size());

    vd g_pos;
    for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
      g_pos.push_back({ getId( i ), i });
    
    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) {
  A.push_back(0);
  idata C( M + 1, - 1 ); // - 1 is the decision tree root
  
  SegTree tree(A);
  
  idata X = tree.X;
  idata Y = tree.Y;

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In constructor 'SegTree::SegTree(idata)':
doll.cpp:52:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = treeIds.size() - size; i < treeIds.size(); i ++)
      |                                         ~~^~~~~~~~~~~~~~~~

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