Submission #1223980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223980		madamadam3	Mechanical Doll (IOI18_doll)	C++20	0 / 100	0 ms	328 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()

typedef long long ll;
using vi = vector<int>;
using pi = pair<int, int>;

void simulate(int m, vi &C, vi &X, vi &Y) {
  int cur = 0, done = 0;
  vi state(X.size(), 0);

  while (true) {
    cout << cur << " ";
    if (cur == 0 && done > 0) break;

    if (cur >= 0) {
      cur = C[cur];
    } else {
      state[(-cur) - 1] = 1 - state[(-cur) - 1];

      if (state[(-cur) - 1] == 1) {
        cur = X[(-cur) - 1];
      } else {
        cur = Y[(-cur) - 1];
      }
    }

    done++;
  }

  cout << "\n";
}

const int POW2[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,524288};

void create_circuit(int m, vi A) {
  int n = sz(A);
  int nsz = 0; while (POW2[nsz+1] <= n) nsz++;

  vi C(m + 1, -1);
  vi X(POW2[nsz+1]-1), Y(POW2[nsz+1]-1);

  int cs = -1, cv = 1;
  queue<pi> q;
  q.push({cs--, 0});

  while (!q.empty()) {
    int cur = q.front().first, cur_depth = q.front().second;
    cur = -cur - 1;
    q.pop();

    if (cur_depth >= nsz) {
      X[cur] = cv++;
      Y[cur] = cv++;
    } else {
      X[cur] = cs--;
      Y[cur] = cs--;
    }

    if (X[cur] < 0) q.push({X[cur], cur_depth+1});
    if (Y[cur] < 0) q.push({Y[cur], cur_depth+1});
  }

  vi order;
  vi state(POW2[nsz+1]-1, 0);
  int cur = -1;
  while (order.size() < cv - 1) {
    int rmcur = -cur - 1;

    if (state[rmcur] == 0) {
      cur = X[rmcur];
    } else {
      cur = Y[rmcur];
    }

    if (cur > 0) {
      order.push_back(cur);
      cur = -1;
    }

    state[rmcur] = 1 - state[rmcur];
  }


  vi to_change(POW2[nsz+1] + 1, -1);
  if (n % 2 == 1) A.push_back(-1), n++;

  int shift = 0; while (order[shift] != A[0] + 1) shift++;
  int curi = 0;
  for (int i = 0; i < n/2; i++) {
    to_change[order[i]] = A[i];
    to_change[order[i+shift]] = A[i+(n/2)];
  }

  to_change[order.back()] = 0;

  for (int i = 0; i < POW2[nsz+1]-1; i++) {
    if (X[i] > 0) X[i] = to_change[X[i]];
    if (Y[i] > 0) Y[i] = to_change[Y[i]];
  }
  
  auto prune = [&](const auto &self, int v) {
    if (X[v] == -1 && Y[v] == -1) {
      return true;
    }

    if (X[v] < -1 && self(self, -X[v]-1)) X[v] = -1;
    if (Y[v] < -1 && self(self, -Y[v]-1)) Y[v] = -1;

    return X[v] == -1 && Y[v] == -1;
  };

  prune(prune, 0);
  int cur_id = 0;
  vi new_order, remapped(X.size());

  auto rename = [&](const auto &self, int v) {
    if (v >= 0) return;
    else v = -v-1;

    remapped[v] = -new_order.size()-1;
    new_order.push_back(-v-1);

    if (X[v] != -1)self(self, X[v]);
    if (Y[v] != -1) self(self, Y[v]);
  };

  rename(rename, -1);

  vi newX(new_order.size()), newY(new_order.size());
  for (int i = 0; i < new_order.size(); i++) {
    int old_id = new_order[i], old_name = -new_order[i]-1;

    newX[i] = X[-old_id-1] >= 0 ? X[-old_id-1] : remapped[-X[-old_id-1]-1];
    newY[i] = Y[-old_id-1] >= 0 ? Y[-old_id-1] : remapped[-Y[-old_id-1]-1];
  }

  X = newX;
  Y = newY;
  simulate(m, C, X, Y);
  answer(C, X, Y);
}

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