random/random_bracket.hpp

View this file on GitHub
Last update: 2026-02-10 00:06:04+09:00
Include: #include "random/random_bracket.hpp"

Depends on

Code

#include "random/shuffle.hpp"

// return: +1,-1 の列
vc<int> random_bracket(int N) {
  vc<int> A(2 * N + 1);
  FOR(i, N + 1) A[i] = 1;
  FOR(i, N + 1, 2 * N + 1) A[i] = -1;
  shuffle(A);
  vc<int> B(2 * N + 2);
  FOR(i, 2 * N + 1) B[i + 1] = B[i] + A[i];
  int k = 0;
  FOR(i, 2 * N + 1) if (B[k] >= B[i]) k = i;
  rotate(A.begin(), A.begin() + k, A.end());
  return A;
}

#line 2 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 2 "random/shuffle.hpp"

template <typename T>
void shuffle(vc<T>& A) {
  FOR(i, len(A)) {
    int j = RNG(0, i + 1);
    if (i != j) swap(A[i], A[j]);
  }
}
#line 2 "random/random_bracket.hpp"

// return: +1,-1 の列
vc<int> random_bracket(int N) {
  vc<int> A(2 * N + 1);
  FOR(i, N + 1) A[i] = 1;
  FOR(i, N + 1, 2 * N + 1) A[i] = -1;
  shuffle(A);
  vc<int> B(2 * N + 2);
  FOR(i, 2 * N + 1) B[i + 1] = B[i] + A[i];
  int k = 0;
  FOR(i, 2 * N + 1) if (B[k] >= B[i]) k = i;
  rotate(A.begin(), A.begin() + k, A.end());
  return A;
}