Submission #993568

#	Time	Username	Problem	Language	Result	Execution time	Memory
993568		poqmen	Mechanical Doll (IOI18_doll)	C++14	100 / 100	84 ms	9556 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

const int START_SENTINEL = 0xdeadbeef;
const int ROOT_SENTINEL = 0x15571557;

void create_circuit(int m, vector<int> a) {
  int n = a.size();
  vector<int> x, y;
  auto add_switch = [&](int sx, int sy) {
    x.push_back(sx);
    y.push_back(sy);
    return -x.size();
  };
  // returns root
  function<int(int, int, int)> construct_t_pow = [&](int sz, int off,
                                                     int stride) -> int {
    if (sz == 1) {
      return off;
    } else {
      int l = construct_t_pow(sz / 2, off, 2 * stride);
      int r = construct_t_pow(sz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    }
  };
  function<int(int, int, int, int)> construct_t = [&](int sz, int csz, int off,
                                                      int stride) -> int {
    if (csz == sz) {
      return construct_t_pow(csz, off, stride);
    }
    if (csz == 1 && sz == 0) return 0;  // the zero-node
    if ((csz / 2) & sz) {
      int l = construct_t_pow(csz / 2, off, 2 * stride);
      int r = construct_t(sz - (csz / 2), csz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    } else {
      int l = ROOT_SENTINEL;  // the root
      int r = construct_t(sz, csz / 2, off + stride, 2 * stride);
      return add_switch(l, r);
    }
  };
  int csz = 2 << __lg(n);
  int root = construct_t(n, csz, 1, 1);
  vector<int> indices;
  for (int i = 0; i < x.size(); ++i) {
    if (x[i] == ROOT_SENTINEL) x[i] = root;
    if (y[i] == ROOT_SENTINEL) y[i] = root;
    if (x[i] > 0) indices.push_back(x[i]);
    if (y[i] > 0) indices.push_back(y[i]);
  }
  sort(indices.begin(), indices.end());
  for (int i = 0; i < x.size(); ++i) {
    if (x[i] > 0)
      x[i] = a[lower_bound(indices.begin(), indices.end(), x[i]) -
               indices.begin()];
    if (y[i] > 0)
      y[i] = a[lower_bound(indices.begin(), indices.end(), y[i]) -
               indices.begin()];
  }
  answer(vector<int>(m + 1, root), x, y);
  return;
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0; i < x.size(); ++i) {
      |                   ~~^~~~~~~~~~
doll.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < x.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