Submission #836737

#	Time	Username	Problem	Language	Result	Execution time	Memory
836737		Johann	Mechanical Doll (IOI18_doll)	C++14	37 / 100	77 ms	14880 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)]);

  int firstSwitch = newSwitch();

  for (int i = 0; i < sz(order); ++i)
    if (order[i].empty())
      C[i] = 0;
    else
      C[i] = firstSwitch;

  vi layer = {firstSwitch};
  while (sz(A) > 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(A) - 1) ? A[idx++] : firstSwitch);
  for (int j = 0; j < sz(layer); ++j)
    setSwitch(Y, layer[j],
              ((idx < sz(A) - 1) || (j == sz(layer) - 1)) ? A[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: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56