結果

問題 No.3673 未来予知
コンテスト
ユーザー akakimidori
提出日時 2026-09-04 23:21:47
言語 C++23(gnu拡張)
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 200 ms
+ 778µs
コード長 1,704 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,935 ms
コンパイル使用メモリ 342,516 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-09-04 23:21:54
合計ジャッジ時間 4,405 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <cassert>

struct xorshift {
    uint32_t seed;
    xorshift() : seed(1231) {}
    xorshift(uint32_t v) : seed(v) {}
    uint32_t operator()() {
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return seed;
    }
};

using namespace std;
template <typename RNG, size_t DEG> auto hack() -> bitset<DEG + 1> {
  RNG rng;
  bitset<DEG + 1> a, b, c;
  b[DEG] = c[DEG] = 1;
  for (size_t l = 0, shift = 1; size_t n : views::iota(0u, DEG * 2)) {
    a >>= 1;
    a[DEG] = rng() & 1;
    if ((c & a).count() % 2 == 0) {
      shift += 1;
      continue;
    }
    auto oc = exchange(c, c ^ (b >> shift));
    if (2 * l <= n) {
      l = n + 1 - l;
      b = oc;
      shift = 1;
    } else {
      shift += 1;
    }
  }
  return c;
}
auto main() -> int {
  constexpr size_t DEG = 100;
  const auto a = hack<xorshift, DEG>();
  std::string t;
  std::cin >> t;
  int n;
  std::cin >> n;
  std::string c = "RSPX";
  std::vector<uint32_t> val(t.size() + n);
  for (int i = 0; i < t.size(); ++i) {
      val[i] = t[i] == 'R' ? 0 : t[i] == 'S' ? 1 : t[i] == 'P' ? 2 : 3;
  }
  for (int i = t.size(); i < val.size(); ++i) {
      uint32_t v = 0;
      for (size_t j = 0; j < DEG; ++j) {
          if (a[j]) v ^= val[i - DEG + j];
      }
      val[i] = v;
      std::cout << c[(v + 3) % 4];
  }
  std::cout << std::endl;
  /*
  uint32_t seed = 0;
  cin >> seed;
  xorshift rng(seed);
  size_t hash = 0;
  for (size_t i = 0; i <= DEG; i += 1) {
    auto h = rng();
    if (a[i]) {
      hash ^= h;
    }
  }
  std::cout << hash << "\n";
  assert(hash == 0);
  */
}

// https://codeforces.com/blog/entry/153335
// ちゃんと理解してない
0