Submission #1222612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222612		madamadam3	자동 인형 (IOI18_doll)	C++20	16 / 100	52 ms	11960 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);
  vi count(m+1, 0);
  vector<vi> nxt(m+1, vi());
  for (int i = 0; i < n; i++) {
    count[A[i]]++;
    if (i != n - 1) nxt[A[i]].push_back(A[i+1]);
    else nxt[A[i]].push_back(0);
  }

  C[0] = A[0];

  vi owner(m+1, 0);
  for (int i = 1; i <= m; i++) {
    if (count[i] <= 0) continue;
    owner[i] = -next_switch()-1;
  }
  for (int i = 1; i <= m; i++) {
    if (count[i] <= 0) continue;

    C[i] = owner[i];

    int a = -owner[i]-1;

    int b = 0, c = 0;
    if (count[i] >= 3) {
      b = next_switch();
      c = next_switch();

      X[a] = -b-1;
      Y[a] = -c-1;
    }

    if (count[i] == 1) {
      X[a] = -a-1;
      Y[a] = nxt[i][0];
    } else if (count[i] == 2) {
      X[a] = nxt[i][0];
      Y[a] = nxt[i][1];
    } else if (count[i] == 3) {
      X[b] = nxt[i][0];
      Y[b] = nxt[i][1];
      X[c] = -a-1;
      Y[c] = nxt[i][2];
    } else if (count[i] == 4) {
      X[b] = nxt[i][0];
      Y[b] = nxt[i][2];
      X[c] = nxt[i][1];
      Y[c] = nxt[i][3];
    }
  }

  // simulate(m, C, X, Y);
  answer(C, X, Y);
  // 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: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56