제출 #620083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
620083		Mamedov	자동 인형 (IOI18_doll)	C++17	53 / 100	99 ms	15396 KiB

doll

#pragma GCC optimize ("O3")
#include "doll.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void create_circuit(int M, vi A) {
  int N = size(A);
  A.eb(0);
  vvi g(M + 1);
  for (int i = 0; i < N; ++i) {
    g[A[i]].eb(A[i + 1]);
  }
  vi C(M + 1, 0), X, Y;
  int S = 0;
  C[0] = A[0];
  for (int i = 1; i <= M; ++i) {
    int ways = size(g[i]);
    if (ways) {
      int pins = 2;
      C[i] = -(S + pins - 1);
      X.eb(oo);
      Y.eb(oo);
      while (pins < ways) {
        for (int j = pins / 2; j < pins; ++j) {
          X[S + j - 1] = -(S + 2 * j);
          Y[S + j - 1] = -(S + 2 * j + 1);
          X.eb(oo);
          Y.eb(oo);
          X.eb(oo);
          Y.eb(oo);
        }
        pins *= 2;
      }
      vi order;
      order.eb(pins);
      int sz = 1;
      while (pins != 1) {
        pins /= 2;
        for (int j = 0; j < sz; ++j) {
          order.eb(order[j] + pins);
        }
        sz *= 2;
      }
      while (!order.empty()) {
        --ways;
        if ((order.back() & 1)) {
          Y[S + order.back() / 2 - 1] = (ways >= 0 ? g[i][ways] : -(S + 1));
        } else {
          X[S + order.back() / 2 - 1] = (ways >= 0 ? g[i][ways] : -(S + 1));
        }
        order.pop_back();
      }
      S = size(X);
    }
  }
  for (int i = 0; i < S; ++i) {
    if (Y[i] == oo) {
      Y[i] = X[i];
      X[i] = -(i + 1);
    }
  }
  answer(C, X, Y);
}

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