結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー ,
提出日時 2026-04-19 17:24:42
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 5,585 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,429 ms
コンパイル使用メモリ 341,588 KB
実行使用メモリ 37,496 KB
最終ジャッジ日時 2026-04-19 17:26:05
合計ジャッジ時間 16,241 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 20 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

static const int WIN[3][3] = {
    {-1, 1, 0},
    { 1,-1, 2},
    { 0, 2,-1},
};

static const int LEX[3] = {1, 0, 2};

const int MAXN  = 200005;
const int MAXND = 400005;

struct Node {
    uint64_t cnt[3];
    int left, right, leaf_pos;
};

static Node nd[MAXND];
static int nc;
static int orig_node[MAXN];
static int leaf_nd[MAXN];
static int par[MAXND];

inline uint64_t sat_add(uint64_t a, uint64_t b, uint64_t cap){
    return (a > cap - b) ? cap : a + b;
}

inline uint64_t sat_mul(uint64_t a, uint64_t b, uint64_t cap){
    if (!a || !b) return 0;
    return (a > cap / b) ? cap : min(cap, a * b);
}

int new_leaf(int pos){
    int id = nc++;
    nd[id] = {{1,1,1}, -1, -1, pos};
    return id;
}

void compute_cnt(int id, uint64_t cap){
    if (nd[id].left == -1){
        nd[id].cnt[0] = nd[id].cnt[1] = nd[id].cnt[2] = 1;
        return;
    }

    int l = nd[id].left, r = nd[id].right;
    nd[id].cnt[0] = nd[id].cnt[1] = nd[id].cnt[2] = 0;

    for (int a = 0; a < 3; a++){
        if (!nd[l].cnt[a]) continue;
        for (int b = 0; b < 3; b++){
            if (a == b || !nd[r].cnt[b]) continue;
            int w = WIN[a][b];
            uint64_t v = sat_mul(nd[l].cnt[a], nd[r].cnt[b], cap);
            nd[id].cnt[w] = sat_add(nd[id].cnt[w], v, cap);
        }
    }
}

static int bit[MAXN], bit_n;

void bit_upd(int i, int v){
    for(; i <= bit_n; i += i & -i) bit[i] += v;
}

int bit_kth(int k){
    int p = 0;
    for(int pw = 1 << 17; pw; pw >>= 1)
        if(p + pw <= bit_n && bit[p + pw] < k){
            p += pw;
            k -= bit[p];
        }
    return p + 1;
}

int build_tree(int N, int* A, uint64_t cap){
    bit_n = N;
    fill(bit + 1, bit + N + 1, 0);

    for(int i = 1; i <= N; i++) bit_upd(i, 1);

    nc = 0;
    for(int i = 1; i <= N; i++) orig_node[i] = new_leaf(i);

    for(int i = 0; i < N - 1; i++){
        int ai = A[i];
        int ol = bit_kth(ai), or_ = bit_kth(ai + 1);

        int nl = orig_node[ol], nr = orig_node[or_];

        int id = nc++;
        nd[id] = {{0,0,0}, nl, nr, -1};
        compute_cnt(id, cap);

        bit_upd(or_, -1);
        orig_node[ol] = id;
    }

    return orig_node[bit_kth(1)];
}

void build_par(int root){
    fill(par, par + nc, -1);
    stack<int> stk;
    stk.push(root);

    while(!stk.empty()){
        int id = stk.top(); stk.pop();
        if(nd[id].left != -1){
            par[nd[id].left] = id;
            par[nd[id].right] = id;
            stk.push(nd[id].left);
            stk.push(nd[id].right);
        }
    }
}

void find_leaves(int root){
    stack<int> stk;
    stk.push(root);

    while(!stk.empty()){
        int id = stk.top(); stk.pop();
        if(nd[id].left == -1)
            leaf_nd[nd[id].leaf_pos] = id;
        else {
            stk.push(nd[id].left);
            stk.push(nd[id].right);
        }
    }
}

static uint64_t live[MAXND][3];
static int asgn[MAXN];

void recompute(int id, uint64_t cap){
    if(nd[id].left == -1){
        int p = nd[id].leaf_pos;
        if(asgn[p] == -1){
            live[id][0] = live[id][1] = live[id][2] = 1;
        } else {
            live[id][0] = live[id][1] = live[id][2] = 0;
            live[id][asgn[p]] = 1;
        }
        return;
    }

    int l = nd[id].left, r = nd[id].right;
    live[id][0] = live[id][1] = live[id][2] = 0;

    for(int a = 0; a < 3; a++){
        if(!live[l][a]) continue;
        for(int b = 0; b < 3; b++){
            if(a == b || !live[r][b]) continue;
            int w = WIN[a][b];
            uint64_t v = sat_mul(live[l][a], live[r][b], cap);
            live[id][w] = sat_add(live[id][w], v, cap);
        }
    }
}

void init_live(int root, uint64_t cap){
    vector<int> order;
    stack<int> stk;
    stk.push(root);

    while(!stk.empty()){
        int id = stk.top(); stk.pop();
        order.push_back(id);
        if(nd[id].left != -1){
            stk.push(nd[id].left);
            stk.push(nd[id].right);
        }
    }

    for(int i = (int)order.size() - 1; i >= 0; i--)
        recompute(order[i], cap);
}

void fix_pos(int pos, int game_c, uint64_t cap){
    asgn[pos] = game_c;
    int id = leaf_nd[pos];
    while(id != -1){
        recompute(id, cap);
        id = par[id];
    }
}

string find_kth(int root, int target, uint64_t K, int N, uint64_t cap){
    fill(asgn + 1, asgn + N + 1, -1);
    init_live(root, cap);

    if(live[root][target] < K) return "-1";

    string res(N, '?');
    const char CH[3] = {'R','P','S'};

    for(int pos = 1; pos <= N; pos++){
        for(int li = 0; li < 3; li++){
            int c = LEX[li];
            fix_pos(pos, c, cap);

            uint64_t cnt = live[root][target];
            if(cnt >= K){
                res[pos - 1] = CH[c];
                break;
            }

            K -= cnt;
            if(li == 2) return "-1";
        }
    }

    return res;
}

static int A[MAXN];

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

    int T;
    cin >> T;

    while(T--){
        int N;
        uint64_t K;
        cin >> N >> K;

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

        uint64_t cap = K;
        int root = build_tree(N, A, cap);

        build_par(root);
        find_leaves(root);

        for(int t = 0; t < 3; t++){
            fill(asgn + 1, asgn + N + 1, -1);
            init_live(root, cap);

            if(live[root][t] < K){
                cout << "-1\n";
            } else {
                cout << find_kth(root, t, K, N, cap) << "\n";
            }
        }
    }

    return 0;
}
0