Submission #836343

#	Time	Username	Problem	Language	Result	Execution time	Memory
836343		Johann	Mechanical Doll (IOI18_doll)	C++14	53 / 100	87 ms	16888 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;
vector<int> X, Y;
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]; }

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

  vi C(M + 1);

  vvi order(M + 1);
  A.push_back(0);
  for (int i = 0; i < sz(A); ++i)
    order[A[i]].push_back(A[(i + 1) % sz(A)]);

  for (int i = 0; i < sz(order); ++i)
  {
    if (order[i].empty())
      C[i] = 0;
    else if (sz(order[i]) == 1)
      C[i] = order[i][0];
    else
    {
      int firstSwitch = newSwitch();
      C[i] = firstSwitch;
      vi layer = {firstSwitch};
      while (sz(order[i]) > 2 * sz(layer))
      {
        vi nlayer;
        // the order of these loops is important!
        for (int s : layer)
        {
          setSwitch(X, s, newSwitch());
          nlayer.push_back(getSwitch(X, s));
        }
        for (int s : layer)
        {
          setSwitch(Y, s, newSwitch());
          nlayer.push_back(getSwitch(Y, s));
        }
        swap(layer, nlayer);
      }

      int idx = 0;
      for (int j = 0; j < sz(layer); ++j)
        setSwitch(X, layer[j],
                  (idx < sz(order[i]) - 1) ? order[i][idx++] : firstSwitch);
      for (int j = 0; j < sz(layer); ++j)
        setSwitch(Y, layer[j],
                  ((idx < sz(order[i]) - 1) || (j == sz(layer) - 1)) ? order[i][idx++] : firstSwitch);
    }
  }

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:29:7: warning: unused variable 'N' [-Wunused-variable]
   29 |   int N = A.size();
      |       ^

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