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

• 問題: No.3510 RPS Eliminations
• ユーザー: Naru820
• 提出日時: 2026-03-18 17:55:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,586 bytes
• コンパイル時間: 2,607 ms
• コンパイル使用メモリ: 348,468 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-17 19:42:07
• 合計ジャッジ時間: 4,143 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

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

ソースコード

// GPT 5.4-pro テスト
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick() {}
    explicit Fenwick(int n): n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    // 1-indexed: 最小の idx で prefix sum >= k
    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (int d = step; d > 0; d >>= 1) {
            int nxt = idx + d;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

struct Mat {
    ull a[3][3]{};
};

struct Solver {
    int N;
    vector<int> A;
    vector<int> L, R, SZ, curNode;
    int root;
    vector<ull> pw2;

    Solver(int N, vector<int> A): N(N), A(move(A)), root(-1) {
        buildTree();
    }

    // 内部表現: P=0, R=1, S=2
    static char charOf(int x) {
        static const char table[3] = {'P', 'R', 'S'};
        return table[x];
    }

    static int lose(int x) {
        // x が勝つ相手
        return (x + 1) % 3;
    }

    static int winner(int x, int y) {
        if (x == y) return -1;
        return (y == lose(x) ? x : y);
    }

    static ull satAdd(ull x, ull y, ull cap) {
        if (x >= cap || y >= cap) return cap;
        if (x > cap - y) return cap;
        return x + y;
    }

    static ull satMul(ull x, ull y, ull cap) {
        if (x == 0 || y == 0) return 0;
        __uint128_t z = (__uint128_t)x * y;
        if (z >= cap) return cap;
        return (ull)z;
    }

    static Mat identity() {
        Mat I;
        for (int i = 0; i < 3; ++i) I.a[i][i] = 1;
        return I;
    }

    static Mat mulMat(const Mat& A, const Mat& B, ull cap) {
        Mat C;
        for (int i = 0; i < 3; ++i) {
            for (int k = 0; k < 3; ++k) {
                if (A.a[i][k] == 0) continue;
                for (int j = 0; j < 3; ++j) {
                    if (B.a[k][j] == 0) continue;
                    C.a[i][j] = satAdd(C.a[i][j], satMul(A.a[i][k], B.a[k][j], cap), cap);
                }
            }
        }
        return C;
    }

    // v[c] = 「その部分木の結果が c になる通り数」
    // y = M(v) x
    static Mat makeMatFromVec(const array<ull, 3>& v) {
        Mat M;
        for (int c = 0; c < 3; ++c) {
            M.a[c][c] = v[lose(c)];
            M.a[c][lose(c)] = v[c];
        }
        return M;
    }

    static Mat makeMatFromFixedValue(int v) {
        array<ull, 3> vec{0, 0, 0};
        vec[v] = 1;
        return makeMatFromVec(vec);
    }

    void preparePowers(ull cap) {
        pw2.assign(N + 1, 1);
        for (int i = 1; i <= N; ++i) pw2[i] = satMul(pw2[i - 1], 2ULL, cap);
    }

    Mat makeMatFromFreeSubtree(int u) const {
        ull t = pw2[SZ[u] - 1];
        return makeMatFromVec({t, t, t});
    }

    optional<string> kthStringForTarget(int target, ull K) {
        preparePowers(K);

        // 固定した 1 文字 target に対して、通り数は常に 2^(N-1)
        if (pw2[N - 1] < K) return nullopt;

        struct Frame {
            int u;
            int state; // 0: 左へ行く前, 1: 左確定済み, 2: 右確定済み
            Mat T;     // 現在の部分木の結果ベクトル -> 根の結果ベクトル
            int valL;  // 左部分木の確定結果
        };

        vector<char> ans(N);
        vector<Frame> st;
        st.reserve(2 * N);
        st.push_back({root, 0, identity(), -2});

        bool hasRet = false;
        int ret = -2;
        ull k = K;

        while (!st.empty()) {
            Frame &f = st.back();
            int u = f.u;

            if (L[u] == -1) {
                int chosen = -1;
                for (int ch = 0; ch < 3; ++ch) { // 辞書順 P < R < S
                    ull cnt = f.T.a[target][ch];
                    if (cnt >= k) {
                        chosen = ch;
                        ans[u] = charOf(ch);
                        break;
                    }
                    k -= cnt;
                }
                if (chosen == -1) return nullopt;

                ret = chosen;
                hasRet = true;
                st.pop_back();
                continue;
            }

            if (f.state == 0) {
                f.state = 1;
                Mat M = makeMatFromFreeSubtree(R[u]);
                st.push_back({L[u], 0, mulMat(f.T, M, K), -2});
                continue;
            }

            if (f.state == 1) {
                if (hasRet) {
                    f.valL = ret;
                    hasRet = false;
                }
                f.state = 2;
                Mat M = makeMatFromFixedValue(f.valL);
                st.push_back({R[u], 0, mulMat(f.T, M, K), -2});
                continue;
            }

            if (hasRet) {
                int valR = ret;
                hasRet = false;
                ret = winner(f.valL, valR);
                hasRet = true;
                st.pop_back();
                continue;
            }

            return nullopt;
        }

        return string(ans.begin(), ans.end());
    }

private:
    void buildTree() {
        int tot = max(1, 2 * N - 1);
        L.assign(tot, -1);
        R.assign(tot, -1);
        SZ.assign(tot, 1);
        curNode.assign(N + 1, -1);

        Fenwick fw(N);
        for (int pos = 1; pos <= N; ++pos) {
            fw.add(pos, 1);
            curNode[pos] = pos - 1;
        }

        int nxt = N;
        for (int ai : A) {
            int p = fw.kth(ai);
            int q = fw.kth(ai + 1);
            int x = curNode[p];
            int y = curNode[q];

            L[nxt] = x;
            R[nxt] = y;
            SZ[nxt] = SZ[x] + SZ[y];

            curNode[p] = nxt; // 左側の位置にマージ結果を残す
            fw.add(q, -1);    // 右側は消える
            ++nxt;
        }

        root = (N == 1 ? 0 : curNode[fw.kth(1)]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ull K;
    cin >> N;
    K = 1; 
    vector<int> A(N - 1);
    for (int i = 0; i < N - 1; ++i) cin >> A[i];

    Solver solver(N, A);

    // 出力順は R, P, S の 3 行
    // 内部表現は P=0, R=1, S=2
    vector<int> targets = {1, 0, 2};

    for (int target : targets) {
        auto ans = solver.kthStringForTarget(target, K);
        if (ans) cout << *ans << '\n';
        else cout << -1 << '\n';
    }

    return 0;
}