Submission #836764

#	Time	Username	Problem	Language	Result	Execution time	Memory
836764		Johann	Mechanical Doll (IOI18_doll)	C++14	100 / 100	88 ms	11104 KiB

doll

#include "doll.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int switches;
vi X, Y;
vi A;
vi L;  // list of leaves
int d; // depth of binary tree

int newSwitch()
{
  X.push_back(0), Y.push_back(0);
  return --switches;
}
void setSwitch(vector<int> &XY, int switchnum, int dest)
{
  XY[-switchnum - 1] = dest;
}
int getSwitch(vector<int> &XY, int i) { return XY[-i - 1]; }
int reverseOrder(int i)
{
  int tmp = 0;
  for (int j = 0; j < d; ++j)
    if ((1 << j) & i)
      tmp |= (1 << (d - j - 1));
  return tmp;
}
int buildTree(int base, int j)
{
  if (j == d)
  {
    int idx = lower_bound(all(L), base) - L.begin();
    return A[idx];
  }
  else
  {
    int sw = newSwitch();
    setSwitch(X, sw, buildTree(base, j + 1));
    setSwitch(Y, sw, buildTree((1 << j) | base, j + 1));
    return sw;
  }
}

void create_circuit(int M, std::vector<int> _A)
{
  A = _A;
  int N = A.size();
  switches = 0;
  vi C(M + 1);

  vi order(M + 1, 0);
  order[0] = 1;
  for (int i = 0; i < sz(A); ++i)
    ++order[A[i]];
  int firstSwitch = newSwitch();
  for (int i = 0; i < sz(order); ++i)
    if (order[i] == 0)
      C[i] = 0;
    else
      C[i] = firstSwitch;

  d = 0;
  while ((1 << d) < N + 1)
    ++d;

  for (int j = 0; j < d; ++j)
  {
    int subtreesize = (1 << (d - j - 1));
    if (N & subtreesize)
      for (int i = 0; i < subtreesize; ++i)
        L.push_back((i << (j + 1)) | ((1 << j) - 1));
  }

  sort(all(L));

  vi line(1, firstSwitch);
  for (int j = 0; j < d; ++j)
  {
    int sw = line[j];
    int base = (1 << j) - 1;

    if (N & (1 << (d - j - 1)))
      setSwitch(X, sw, buildTree(base, j + 1));
    else
      setSwitch(X, sw, firstSwitch);

    if (j < d - 1)
    {
      line.push_back(newSwitch());
      setSwitch(Y, sw, line.back());
    }
    else
      setSwitch(Y, sw, 0);
  }

  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: 56 / 56