제출 #1222606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222606		madamadam3	자동 인형 (IOI18_doll)	C++20	47 / 100	74 ms	12076 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};

vi X, Y, C;
int cur = 0;

int next_switch() {
  X.resize(X.size() + 1);
  Y.resize(Y.size() + 1);

  cur--;
  return -cur -1;
}

void create_circuit(int m, vi A) {
  C.assign(m+1, -1);
  int n = sz(A);
  bool subbed = n % 2 == 0;
  if (subbed) n--;
  int L = 1; while ((L*2) <= n) L*=2;

  vi nodes; int cur_pos = 1;
  for (int i = 0; i < L; i++) {
    int cc = next_switch();

    X[cc] = cur_pos++;
    Y[cc] = cur_pos++;

    nodes.push_back(cur);
  }

  while (nodes.size() > 1) {
    vi new_nodes;

    while (nodes.size() > 1) {
      int a = nodes.back(); nodes.pop_back();
      int b = nodes.back(); nodes.pop_back();

      int par = next_switch();
      X[par] = a;
      Y[par] = b;

      new_nodes.push_back(cur);
    }

    if (nodes.size() == 1) {
      new_nodes.push_back(nodes.back());
      nodes.pop_back();
    }

    nodes = new_nodes;
  }

  int root = nodes[0];
  // for (int i = 0; i < -cur; i++) {
  //   cout << (-i-1) << " " << X[i] << "\n";
  //   cout << (-i-1) << " " << Y[i] << "\n";
  // }

  vi order;
  vi state(-cur+1, 0);

  int cnode = root;
  while(order.size() < cur_pos-1) {
    int rcnode = -cnode - 1;

    if (state[rcnode] == 0) {
      cnode = X[rcnode];
    } else {
      cnode = Y[rcnode];
    }

    state[rcnode] = 1 - state[rcnode];

    if (cnode > 0) {
      order.push_back(cnode);
      cnode = root;
    }
  }

  vi to_swap(cur_pos, -1);
  for (int i = 0; i < cur_pos - 1; i++) {
    if (i < n) {
      to_swap[order[i]] = A[subbed ? i + 1 : i];
    } else if (i < cur_pos - 2) {
      to_swap[order[i]] = root;
    } else {
      to_swap[order[i]] = 0;
    }
  }

  for (int i = 0; i < -cur; i++) {
    if (X[i] > 0) X[i] = to_swap[X[i]];
    if (Y[i] > 0) Y[i] = to_swap[Y[i]];
  }

  C.assign(m+1, root);
  if (subbed) C[0] = A[0];
  // simulate(m,C, X, Y);
  answer(C, X, Y);
}

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