Submission #1244890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244890		Boas	Mechanical Doll (IOI18_doll)	C++20	2 / 100	53 ms	10260 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);
  loop(sz(A), 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;
        while (cnt < sz(occ[A[i]]))
        {
          pow++;
          cnt *= 2;
        }
        int startIx = S;
        S += cnt - 1;
        loop(cnt - 1, ix)
        {
          X.pb({});
          Y.pb({});
        }
        for (int ix : occ[A[i]])
        {
          C[ix] = -startIx;
        }
        for (int ix = 1; ix <= cnt; ix++)
        {
          int l = 2 * ix, r = 2 * ix + 1;
          if (l >= cnt)
          {
            X[startIx + (ix - 1)] = occ[A[i]][trees[pow][l - cnt]];
            Y[startIx + (ix - 1)] = occ[A[i]][trees[pow][r - cnt]];
          }
          else
          {
            X[startIx + (ix - 1)] = -(startIx + (l - 1));
            Y[startIx + (ix - 1)] = -(startIx + (r - 1));
          }
        }
      }
    }
    curOcc[A[i]]++;
  }
  for (int &i : C)
    if (i == -1 && S == 0)
      i = 0;
  answer(C, X, Y);
}

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