Submission #415420

#	Time	Username	Problem	Language	Result	Execution time	Memory
415420		2qbingxuan	Mechanical Doll (IOI18_doll)	C++17	39 / 100	130 ms	13368 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#ifdef local
#define debug(x...) qqbx(#x, x)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\e[1;32m(" << s << ") = ("), ... , (std::cerr << a << (--cnt ? ", " : "\e[0m)\n")));
}
#define pary(x...) danb(#x, x)
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        std::cerr << (f++ ? ", " : "") << *L;
    std::cerr << " ]\e[0m\n";
}
#else
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)

using namespace std;
const int maxn = 800025;

int odd[maxn];
int ls[maxn], rs[maxn];
int leaf[maxn];
int counter = 0;
int build(int l, int r, int a, int b) {
    int cur = counter++;
    if (l+1 == r) {
        leaf[cur] = b;
        debug(cur, leaf[cur]);
        return cur;
    }
    leaf[cur] = -1;
    int m = l+(r-l)/2;
    ls[cur] = build(l, m, a*2, b);
    rs[cur] = build(m, r, a*2, b+a);
    return cur;
}
void create_circuit(int M, std::vector<int> A) {

  int N = A.size();
  vector<int> cnt(M + 1);
  for (int i = 0; i < N; i++) cnt[A[i]] += 1;
  vector<int> tmp;
  for (int i = 0; i < N; i++) {
      if (cnt[A[i]] != 1) {
          tmp.push_back(i);
      }
  }
  pary(all(tmp));

  int S = 0;
  while ((1<<S) * 2 - 1 < (int)tmp.size()) ++S;
  int H = 1 << S;

  int root = build(0, H, 1, 0);

  std::vector<int> C(M + 1, -root-1);
  std::vector<int> X(counter), Y(counter);

  for (int i = 0; i < N; i++) {
      if (cnt[A[i]] == 1) {
          C[A[i]] = i+1<N ? A[i+1] : 0;
      }
  }
  auto f = [&](int idx) {
      if (idx == H * 2 - 1) {
          if (tmp.empty())
              return A[0];
          else if (tmp.back() == N-1)
              return 0;
          else
              return A[tmp.back() + 1];
      }
      if (idx < (int)tmp.size()) {
          debug(idx);
          return idx ? A[tmp[idx-1] + 1] : A[0];
      }
      return -root-1;
  };
  for (int i = 0; i < counter; i++) {
      if (leaf[i] != -1) {
          X[i] = f(leaf[i]);
          Y[i] = f(leaf[i] + H);
      } else {
          X[i] = -ls[i]-1;
          Y[i] = -rs[i]-1;
      }
  }

  /*
  int cur = root;
  for (int cnt = 0; cnt < N*2; ) {
      if (leaf[cur] != -1) {
          debug(cur, leaf[cur], odd[cur]);
          // pary(odd, odd+counter);
          ++cnt;
      }
      int nxt = odd[cur] ? rs[cur] : ls[cur];
      odd[cur] ^= 1;
      cur = nxt;
  }
  */

  answer(C, X, Y);
}

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