Submission #1244929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244929		Boas	Mechanical Doll (IOI18_doll)	C++20	6 / 100	68 ms	13832 KiB

doll

#include "doll.h"

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

#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

void create_circuit(int M, vi A)
{
  vvi trees(19);
  for (int i = 1, cnt = 2; i <= 18; i++)
  {
    // cnt - 1 switches indexed 1 .. cnt-1
    vb x(cnt);
    while (sz(trees[i]) < cnt)
    {
      int j = 1;
      while (j < cnt)
      {
        x[j].flip();
        if (!x[j])
          j = 2 * j + 1;
        else
          j *= 2;
      }
      trees[i].pb(j - cnt);
    }
    cnt *= 2;
  }
  int N = sz(A);
  A.pb(0);
  vvi occ(M + 1); // volgende
  loop(N, ix)
  {
    occ[A[ix]].pb(A[ix + 1]);
  }

  vi C(M + 1, -1);
  C[0] = A[0];
  int S = 0;
  vi X, Y;
  vi curOcc(M + 1);
  loop(N, i)
  {
    if (sz(occ[A[i]]) == 1)
    {
      C[A[i]] = A[i + 1];
    }
    else
    {
      if (curOcc[A[i]] == 0)
      {
        int pow = 1;
        int cnt = 2;
        int actualCnt = sz(occ[A[i]]);
        while (2 * cnt <= sz(occ[A[i]]))
        {
          pow++;
          cnt *= 2;
        }
        int extra = actualCnt - cnt;
        int startIx = S;
        S += actualCnt - 1;
        loop(actualCnt - 1, ix)
        {
          X.pb({});
          Y.pb({});
        }
        C[A[i]] = -startIx - 1;
        for (int ix = 1; ix < actualCnt; ix++)
        {
          int l = 2 * ix, r = 2 * ix + 1;
          if (l >= cnt)
          {
            int occixl, occixr;
            if (ix >= cnt)
            {
              occixl = trees[pow][ix - cnt];
              occixr = trees[pow][ix - cnt] + cnt;
            }
            else
            {
              occixl = trees[pow][l - cnt];
              occixr = trees[pow][r - cnt];
            }
            if (occixl < extra && ix < cnt)
              X[startIx + (ix - 1)] = -(1 + startIx + (l - 1));
            else
              X[startIx + (ix - 1)] = occ[A[i]][occixl];

            if (occixr < extra)
              Y[startIx + (ix - 1)] = -(1 + startIx + (r - 1));
            else
              Y[startIx + (ix - 1)] = occ[A[i]][occixr];
          }
          else
          {
            X[startIx + (ix - 1)] = -(1 + startIx + (l - 1));
            Y[startIx + (ix - 1)] = -(1 + startIx + (r - 1));
          }
        }
      }
    }
    curOcc[A[i]]++;
  }
  for (int &i : C)
    if (i == -1 && S == 0)
      i = 0;
  for (int i : C)
    if (i < -S || i > M)
      throw;
  for (int i : X)
    if (i < -S || i > M)
      throw;
  for (int i : Y)
    if (i < -S || i > M)
      throw;
  answer(C, X, Y);
}

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