Submission #1222452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222452		madamadam3	Mechanical Doll (IOI18_doll)	C++20	37 / 100	143 ms	12404 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);
  int cur_idx = 0;

  for (int i = 0; i < n; i++) {
    to_change[order[cur_idx++]] = A[i];
  }

  while (cur_idx < order.size() - 1) {
    to_change[order[cur_idx++]] = -1;
  }

  to_change[order[cur_idx]] = 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]];
  }

  // for (auto &el : X) if (el >= -1) cout << el << " "; cout << "\n";
  // for (auto &el : Y) if (el >= -1) cout << el << " "; cout << "\n";

  // 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: 9 / 18
• Subtask 6: 28 / 56