結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー ガルム
提出日時 2026-04-18 13:32:21
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 6,149 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,101 ms
コンパイル使用メモリ 205,844 KB
実行使用メモリ 48,920 KB
最終ジャッジ日時 2026-04-18 13:32:28
合計ジャッジ時間 6,073 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::{self, Read};

const LIM: u128 = 1_000_000_000_000_000_000;
const NONE: usize = usize::MAX;
const CH: [u8; 3] = [b'P', b'R', b'S'];

#[derive(Clone)]
struct Node {
    l: usize,
    r: usize,
    cnt: [u128; 3],
}

struct Bit {
    n: usize,
    bit: Vec<i64>,
}

impl Bit {
    fn new(n: usize) -> Self {
        Self {
            n,
            bit: vec![0; n + 1],
        }
    }

    fn add(&mut self, mut i: usize, x: i64) {
        while i <= self.n {
            self.bit[i] += x;
            i += i & (!i + 1);
        }
    }

    fn kth(&self, mut k: i64) -> usize {
        let mut idx = 0usize;
        let mut w = 1usize;
        while (w << 1) <= self.n {
            w <<= 1;
        }
        while w > 0 {
            let ni = idx + w;
            if ni <= self.n && self.bit[ni] < k {
                idx = ni;
                k -= self.bit[ni];
            }
            w >>= 1;
        }
        idx + 1
    }
}

struct Scanner {
    buf: Vec<u8>,
    idx: usize,
}

impl Scanner {
    fn new() -> Self {
        let mut input = Vec::new();
        io::stdin().read_to_end(&mut input).unwrap();
        Self { buf: input, idx: 0 }
    }

    fn usize(&mut self) -> usize {
        while self.idx < self.buf.len() && self.buf[self.idx].is_ascii_whitespace() {
            self.idx += 1;
        }
        let mut res = 0usize;
        while self.idx < self.buf.len() && !self.buf[self.idx].is_ascii_whitespace() {
            res = res * 10 + (self.buf[self.idx] - b'0') as usize;
            self.idx += 1;
        }
        res
    }

    fn u128(&mut self) -> u128 {
        while self.idx < self.buf.len() && self.buf[self.idx].is_ascii_whitespace() {
            self.idx += 1;
        }
        let mut res = 0u128;
        while self.idx < self.buf.len() && !self.buf[self.idx].is_ascii_whitespace() {
            res = res * 10 + (self.buf[self.idx] - b'0') as u128;
            self.idx += 1;
        }
        res
    }
}

fn win(a: usize, b: usize) -> usize {
    if (a + 1) % 3 == b {
        a
    } else {
        b
    }
}

fn add_cap(a: u128, b: u128) -> u128 {
    (a + b).min(LIM)
}

fn mul_cap(a: u128, b: u128) -> u128 {
    (a * b).min(LIM)
}

fn cnt_node(nodes: &[Node], l: usize, r: usize) -> [u128; 3] {
    let mut res = [0u128; 3];
    for x in 0..3 {
        let y = (x + 1) % 3;
        let v1 = mul_cap(nodes[l].cnt[x], nodes[r].cnt[y]);
        let v2 = mul_cap(nodes[l].cnt[y], nodes[r].cnt[x]);
        res[x] = add_cap(v1, v2);
    }
    res
}

fn left_weight(nodes: &[Node], r: usize, w: [u128; 3]) -> [u128; 3] {
    let mut res = [0u128; 3];
    for lc in 0..3 {
        let mut now = 0u128;
        for rc in 0..3 {
            if lc == rc {
                continue;
            }
            let p = win(lc, rc);
            now = add_cap(now, mul_cap(nodes[r].cnt[rc], w[p]));
        }
        res[lc] = now;
    }
    res
}

fn right_weight(lc: usize, w: [u128; 3]) -> [u128; 3] {
    let mut res = [0u128; 3];
    for rc in 0..3 {
        if lc != rc {
            res[rc] = w[win(lc, rc)];
        }
    }
    res
}

enum Frame {
    Enter {
        v: usize,
        w: [u128; 3],
        k: u128,
    },
    AfterLeft {
        v: usize,
        w: [u128; 3],
    },
    AfterRight {
        lc: usize,
    },
}

fn restore(nodes: &[Node], root: usize, target: usize, k: u128) -> Option<String> {
    if nodes[root].cnt[target] < k {
        return None;
    }

    let mut ans = Vec::new();
    let mut ret = (0usize, 0u128);
    let mut w0 = [0u128; 3];
    w0[target] = 1;
    let mut st = vec![Frame::Enter { v: root, w: w0, k }];

    while let Some(fr) = st.pop() {
        match fr {
            Frame::Enter { v, w, mut k } => {
                if nodes[v].l == NONE {
                    for c in 0..3 {
                        if k <= w[c] {
                            ans.push(CH[c]);
                            ret = (c, k);
                            break;
                        }
                        k -= w[c];
                    }
                } else {
                    let l = nodes[v].l;
                    let r = nodes[v].r;
                    let lw = left_weight(nodes, r, w);
                    st.push(Frame::AfterLeft { v, w });
                    st.push(Frame::Enter { v: l, w: lw, k });
                }
            }
            Frame::AfterLeft { v, w } => {
                let (lc, k2) = ret;
                let rw = right_weight(lc, w);
                st.push(Frame::AfterRight { lc });
                st.push(Frame::Enter {
                    v: nodes[v].r,
                    w: rw,
                    k: k2,
                });
            }
            Frame::AfterRight { lc } => {
                let (rc, k2) = ret;
                ret = (win(lc, rc), k2);
            }
        }
    }

    Some(String::from_utf8(ans).unwrap())
}

fn main() {
    let mut sc = Scanner::new();
    let t = sc.usize();
    let mut out = Vec::new();

    for _ in 0..t {
        let n = sc.usize();
        let k = sc.u128();
        let mut a = vec![0usize; n - 1];
        for i in 0..n - 1 {
            a[i] = sc.usize();
        }

        let mut bit = Bit::new(n);
        let mut id = vec![0usize; n + 1];
        let mut nodes = Vec::with_capacity(2 * n - 1);

        for i in 1..=n {
            bit.add(i, 1);
            id[i] = i - 1;
            nodes.push(Node {
                l: NONE,
                r: NONE,
                cnt: [1, 1, 1],
            });
        }

        for x in a {
            let p = bit.kth(x as i64);
            let q = bit.kth(x as i64 + 1);
            let l = id[p];
            let r = id[q];
            let cnt = cnt_node(&nodes, l, r);
            let v = nodes.len();
            nodes.push(Node { l, r, cnt });
            id[p] = v;
            bit.add(q, -1);
        }

        let root = nodes.len() - 1;
        for target in [1usize, 0, 2] {
            match restore(&nodes, root, target, k) {
                Some(s) => out.push(s),
                None => out.push("-1".to_string()),
            }
        }
    }

    println!("{}", out.join("\n"));
}
0