#1151879 (C++23) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: Nzt3
• 提出日時: 2026-03-07 18:41:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,196 bytes
• コンパイル時間: 6,298 ms
• コンパイル使用メモリ: 367,660 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-04-17 19:33:01
• 合計ジャッジ時間: 13,413 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	WA * 1
other	WA * 28

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto &&e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  segtree(int n) : segtree(vector<S>(n, e())) {}
  segtree(const vector<S> &v) : n(sz(v)) {
    s = bit_ceil(unsigned(n));
    log = countr_zero(unsigned(s));
    d = vector<S>(2 * s, e());
    rep(i, n) d[s + i] = v[i];
    per(i, s, 1) update(i);
  } // d655ce82
  void set(int p, S x) {
    d[p += s] = x;
    rep(i, 1, log + 1) update(p >> i);
  } // 255c3505
  S prod(int l, int r) const {
    S sml = e(), smr = e();
    l += s, r += s;
    while (l < r) {
      if (l & 1)
        sml = op(sml, d[l++]);
      if (r & 1)
        smr = op(d[--r], smr);
      l >>= 1, r >>= 1;
    }
    return op(sml, smr);
  } // 6f0dc967
  S all_prod() const { return d[1]; }
  S get(int p) const { return d[s + p]; }
  template <typename F> int max_right(int l, F f) const {
    if (l == n)
      return n;
    l += s;
    S sm = e();
    do {
      while (~l & 1)
        l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < s) {
          l <<= 1;
          if (f(op(sm, d[l])))
            sm = op(sm, d[l++]);
        }
        return l - s;
      }
      sm = op(sm, d[l++]);
    } while ((l & -l) != l);
    return n;
  } // 9291fa12
  template <typename F> int min_left(int r, F f) const {
    if (!r)
      return 0;
    r += s;
    S sm = e();
    do {
      r--;
      while (r > 1 and r & 1)
        r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < s) {
          r = (2 * r + 1);
          if (f(op(d[r], sm)))
            sm = op(d[r--], sm);
        }
        return r + 1 - s;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  } // 8a9e706b
private:
  int n, s, log;
  vector<S> d;
  void update(int k) { d[k] = op(d[k * 2], d[k * 2 + 1]); }
};

int seg_op(int a, int b) { return a + b; }
int seg_e() { return 0; }

int main() {
  int N;
  cin >> N;
  vi A(N - 1);
  fore(i, A) cin >> i;
  segtree<int, seg_op, seg_e> s(N);
  rep(i, N) { s.set(i, 1); }
  vi p, idx(N);
  iota(all(idx), 0);
  p.reserve(N * 2);
  vector<pii> G;
  G.reserve(N * 2);
  rep(i, N) G.push_back(pii{-1, -1});
  s.set(0, 1);
  for (int v : A) {
    auto l = [&](int x) { return x < v; };
    auto r = [&](int x) { return x < v + 1; };
    int t1 = s.max_right(0, l), t2 = s.max_right(0, r);
    p[idx[t1]] = p[idx[t2]] = N + sz(G);
    G.push_back(pii{idx[t1], idx[t2]});
    idx[t2] = -1;
    idx[t1] = sz(G) - 1;
    s.set(t2, 0);
  }
  // {
  //   // グラフの形を確認
  //   vector<pii> E;
  //   rep(i, sz(G)) {
  //     if (G[i].first != -1)
  //       E.push_back(pii{i, G[i].first});
  //     if (G[i].second != -1)
  //       E.push_back(pii{i, G[i].second});
  //   }
  //   cout << "---------- DEBUG BEGIN ----------\n";

  //   cout << sz(G) << ' ' << sz(E) << '\n';
  //   for (auto [u, v] : E)
  //     cout << u << ' ' << v << '\n';
  //   cout << "---------- DEBUG END ----------\n";
  // }

  vector<array<int, 3>> lexOrd(sz(G));
  vector<array<pii, 3>> lexChild(sz(G));

  // P -> 0, R -> 1, S -> 2
  auto janken = [&](int a, int b) -> int {
    if (a == b)
      return -1;
    switch (a) {
    case 0: {
      if (b == 1)
        return 0;
      else if (b == 2)
        return 2;
      break;
    }
    case 1: {
      if (b == 0)
        return 0;
      else if (b == 2)
        return 1;
      break;
    }
    case 2: {
      if (b == 0)
        return 2;
      else if (b == 1)
        return 1;
      break;
    }
    }
    return -1;
  };

  rep(i, sz(G)) { lexOrd[i] = {0, 1, 2}; }

  stack<int> dfs;
  dfs.push(N * 2 - 2);
  vi used(N * 2);
  while (!dfs.empty()) {
    int v = dfs.top();
    dfs.pop();
    used[v] = 1;
    if (G[v].first == -1) {
      continue;
    }
    auto [c1, c2] = G[v];
    if (!used[c1]) {
      dfs.push(v);
      dfs.push(c1);
      continue;
    }
    if (!used[c2]) {
      dfs.push(v);
      dfs.push(c2);
      continue;
    }
    array<int, 3> existflag{0, 0, 0};
    lexOrd[v] = {-1, -1, -1};
    // cerr<<format("v={},c1={},c2={}\n",v,c1,c2);
    rep(i, 3) {
      rep(j, 3) {
        char r = janken(lexOrd[c1][i], lexOrd[c2][j]);
        if (r == -1)
          continue;
        if (!existflag[r]) {
          existflag[r] = 1;
          rep(k, 3) {
            if (lexOrd[v][k] == -1) {
              lexOrd[v][k] = r;
              lexChild[v][r] = pii{lexOrd[c1][i], lexOrd[c2][j]};
              break;
            }
          }
        }
      }
    }
  }

  // rep(i,sz(G)){
  //   cerr<<i<<":\n";
  //   rep(j,3)cerr<<lexOrd[i][j]<<lexChild[i][lexOrd[i][j]].first<<lexChild[i][lexOrd[i][j]].second<<'
  //   '; cerr<<endl; cerr<<G[i].first<<' '<<G[i].second<<endl;
  // }

  string ord2char = "PRS";
  array<string, 3> ans;
  rep(fS, 3) {
    string S(N, '/');
    queue<pii> bfs;
    bfs.push(pii{sz(G) - 1, fS});
    while (!bfs.empty()) {
      auto [v, c] = bfs.front();
      bfs.pop();
      if (v < N) {
        S[v] = ord2char[c];
        continue;
      }
      int u1 = G[v].first;
      int u2 = G[v].second;
      bfs.push(pii{u1, lexChild[v][c].first});
      bfs.push(pii{u2, lexChild[v][c].second});
    }
    ans[fS] = S;
  }
  cout << format("{}\n{}\n{}\n", ans[1], ans[0], ans[2]);
}