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

• 問題: No.3510 RPS Eliminations
• ユーザー: 왕지후
• 提出日時: 2026-04-18 12:16:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,866 bytes
• コンパイル時間: 2,304 ms
• コンパイル使用メモリ: 347,996 KB
• 実行使用メモリ: 51,980 KB
• 最終ジャッジ日時: 2026-04-18 12:16:53
• 合計ジャッジ時間: 12,619 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	-- * 1
other	AC * 20 TLE * 1 -- * 7

ソースコード

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

using int64 = long long;
static const unsigned long long LIM = (unsigned long long)4e18;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick() {}
    Fenwick(int n): n(n), bit(n+1,0) {}
    void add(int i, int v){
        for(; i<=n; i+=i&-i) bit[i]+=v;
    }
    int sumPrefix(int i) const {
        int r=0;
        for(; i>0; i-=i&-i) r+=bit[i];
        return r;
    }
    int kth(int k) const { // 1-indexed kth alive
        int idx=0;
        int pw=1;
        while((pw<<1)<=n) pw<<=1;
        for(int d=pw; d; d>>=1){
            int ni=idx+d;
            if(ni<=n && bit[ni]<k){
                idx=ni;
                k-=bit[ni];
            }
        }
        return idx+1;
    }
};

struct Node {
    int l=-1, r=-1, p=-1;
    array<unsigned long long,3> dp{0,0,0};
    int leafPos=-1; // 1..N for leaves, else -1
};

static inline int loseTo(int x){
    // 0:R, 1:P, 2:S
    // R beats S, P beats R, S beats P
    // so loser beaten by x:
    if(x==0) return 2; // R beats S
    if(x==1) return 0; // P beats R
    return 1;          // S beats P
}

static inline unsigned long long capMul(unsigned long long a, unsigned long long b){
    __uint128_t z = (__uint128_t)a * (__uint128_t)b;
    if(z > LIM) return LIM;
    return (unsigned long long)z;
}
static inline unsigned long long capAdd(unsigned long long a, unsigned long long b){
    unsigned long long c = a + b;
    if(c < a || c > LIM) return LIM;
    return c;
}

void pull(vector<Node>& tr, int u){
    if(tr[u].l==-1 && tr[u].r==-1) return;
    auto &L = tr[tr[u].l].dp;
    auto &R = tr[tr[u].r].dp;
    for(int t=0;t<3;t++){
        int z = loseTo(t);
        unsigned long long v = 0;
        v = capAdd(v, capMul(L[t], R[z]));
        v = capAdd(v, capMul(L[z], R[t]));
        tr[u].dp[t] = v;
    }
}

void setLeafUnknown(vector<Node>& tr, int u){
    tr[u].dp = {1,1,1};
}
void setLeafFixed(vector<Node>& tr, int u, int c){
    tr[u].dp = {0,0,0};
    tr[u].dp[c] = 1;
}

string buildSlow(vector<Node> tr, int root, const vector<int>& leafId, int target, unsigned long long K){
    // Slow constructor: fix leaves from left to right, update to root each time.
    // Correct but worst-case O(N^2).
    int N = (int)leafId.size() - 1;
    if(tr[root].dp[target] < K) return "-1";

    string ans;
    ans.reserve(N);

    auto updatePath = [&](int u){
        while(u!=-1){
            if(!(tr[u].l==-1 && tr[u].r==-1)) pull(tr,u);
            u = tr[u].p;
        }
    };

    // start: all leaves unknown
    for(int i=1;i<=N;i++){
        int leaf = leafId[i];
        int chosen = -1;

        // lexicographic order over characters is 'P' < 'R' < 'S'
        vector<pair<char,int>> order = {{'P',1},{'R',0},{'S',2}};
        for(auto [ch,col] : order){
            setLeafFixed(tr, leaf, col);
            updatePath(tr[leaf].p);

            unsigned long long cnt = tr[root].dp[target];
            if(cnt >= K){
                ans.push_back(ch);
                chosen = col;
                break;
            }else{
                K -= cnt;
            }
        }

        if(chosen==-1) return "-1";

        // keep chosen fixed, continue
    }

    return ans;
}

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

    int T;
    cin >> T;
    while(T--){
        int N;
        unsigned long long K;
        cin >> N >> K;
        vector<int> A(N);
        for(int i=1;i<=N-1;i++) cin >> A[i];

        // Build merge tree
        // current alive items are represented by positions 1..N in original order.
        // merged node stays at the left item's position; right item is removed.
        vector<Node> tr(2*N+5);
        int ptr = N;

        vector<int> rootAtPos(N+1);
        for(int i=1;i<=N;i++){
            rootAtPos[i]=i;
            tr[i].leafPos=i;
            tr[i].dp = {1,1,1}; // initially unknown leaf
        }

        Fenwick fw(N);
        for(int i=1;i<=N;i++) fw.add(i,1);

        for(int step=1; step<=N-1; step++){
            int k = A[step];
            int posL = fw.kth(k);
            int posR = fw.kth(k+1);

            int leftRoot = rootAtPos[posL];
            int rightRoot = rootAtPos[posR];

            ++ptr;
            tr[ptr].l = leftRoot;
            tr[ptr].r = rightRoot;
            tr[leftRoot].p = ptr;
            tr[rightRoot].p = ptr;
            pull(tr, ptr);

            rootAtPos[posL] = ptr;
            fw.add(posR, -1);
        }

        int alivePos = fw.kth(1);
        int root = rootAtPos[alivePos];

        vector<int> leafId(N+1);
        for(int i=1;i<=N;i++) leafId[i]=i;

        // target order in output: R, P, S
        cout << buildSlow(tr, root, leafId, 0, K) << '\n';
        cout << buildSlow(tr, root, leafId, 1, K) << '\n';
        cout << buildSlow(tr, root, leafId, 2, K) << '\n';
    }
    return 0;
}