結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-04-18 17:53:14 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 105 ms / 2,000 ms |
| コード長 | 9,251 bytes |
| 記録 | |
| コンパイル時間 | 11,117 ms |
| コンパイル使用メモリ | 215,456 KB |
| 実行使用メモリ | 46,140 KB |
| 最終ジャッジ日時 | 2026-04-18 17:53:37 |
| 合計ジャッジ時間 | 9,283 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
コンパイルメッセージ
warning: type alias `Map` is never used
--> src/main.rs:145:6
|
145 | type Map<K, V> = BTreeMap<K, V>;
| ^^^
|
= note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default
warning: type alias `Set` is never used
--> src/main.rs:146:6
|
146 | type Set<T> = BTreeSet<T>;
| ^^^
warning: type alias `Deque` is never used
--> src/main.rs:147:6
|
147 | type Deque<T> = VecDeque<T>;
| ^^^^^
ソースコード
// まず全体で何通りあるかという問題は解けるか
// 操作過程を木と見ればDPで計算できる
// 辞書順？
// STTで葉を固定しつ計算できる？
//
// point
// 3状態
// path
// 葉と3*3
//
// まあできるはできるが2N のSTTに 3*3行列積乗っけて3回解くのは間に合うのか？
// かなり怪しい気がする
//
// 操作が隣接する文字についてのみなことが重要？
// Pを生成するには
// PR or RP
// 通りの数自体は2冪か
//
// Kを0-indexedとしておく
// Pを作りたい
// left, right で左右の葉の個数
// P, R を合わせてK/2^(right-1)番目の物をleftで生成
// 対応するものをrightで生成
//
// P,R合わせてK番目のものを生成したい時
// PR, RP, RS, SR のどれか
// ...
// 重みをつけながら再帰していく感じで前から構築できそう?
fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
let t: u32 = sc.next();
for _ in 0..t {
let n: usize = sc.next();
let k = sc.next::<u64>() - 1;
let a = sc.next_vec::<usize>(n - 1);
if k >= 1 << (n - 1).min(60) {
for _ in 0..3 {
writeln!(out, "-1").ok();
}
continue;
}
let mut seg = SegmentTreePURQ::new(n, 0, |a, b| *a + *b);
for i in 0..n {
seg.update_tmp(i, 1);
}
seg.update_all();
let mut child = vec![(2 * n, 2 * n); n + n - 1];
let mut vertex = (0..n).collect::<Vec<_>>();
let mut size = vec![0; child.len()];
size[..n].fill(1);
for (i, &a) in a.iter().enumerate() {
let l = seg.max_right(0, |p| *p < a);
let r = seg.max_right(0, |p| *p < a + 1);
child[n + i] = (vertex[l], vertex[r]);
size[n + i] = size[vertex[l]] + size[vertex[r]];
vertex[l] = n + i;
seg.update(r, 0);
}
let c = ['P', 'R', 'S'];
for &x in [1, 0, 2].iter() {
let inf = 10u64.pow(18) + 1;
let ans = std::cell::RefCell::new(String::new());
let k = std::cell::RefCell::new(k);
let mut weight = [0; 3];
weight[x] += 1;
recurse(|rec, (v, weight): (usize, [u64; 3])| -> usize {
//println!("{v}: {:?} {:?} {:?}", weight, ans.borrow(), k.borrow());
if v < n {
let mut k = k.borrow_mut();
for (i, w) in weight.iter().enumerate() {
if *k >= *w {
*k -= *w;
} else {
ans.borrow_mut().push(c[i]);
return i;
}
}
unreachable!();
}
let (l, r) = child[v];
let mul = 1u64 << (size[r] - 1).min(60);
let mut nweight = [0; 3];
for (i, &w) in weight.iter().enumerate() {
for &j in [i, (i + 1) % 3].iter() {
nweight[j] = (nweight[j] + w.saturating_mul(mul).min(inf)).min(inf);
}
}
let res = rec((l, nweight));
let mut nw = [0; 3];
for i in 0..3 {
if i == res {
continue;
}
let op = if res == (i + 1) % 3 {
i
} else {
res
};
nw[i] = weight[op];
}
let r = rec((r, nw));
if res == (r + 1) % 3 {
r
} else {
res
}
})((child.len() - 1, weight));
writeln!(out, "{}", ans.borrow()).ok();
}
}
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
// ---------- end scannner ----------
use std::collections::*;
use std::io::Write;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
run(&mut sc, &mut out);
}
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
n: usize,
size: usize,
data: Vec<T>,
e: T,
op: F,
}
impl<T, F> SegmentTreePURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(n: usize, e: T, op: F) -> Self {
assert!(n > 0);
let size = n.next_power_of_two();
let data = vec![e.clone(); 2 * size];
SegmentTreePURQ {
n,
size,
data,
e,
op,
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.n);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
for i in (1..self.size).rev() {
self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.n);
let mut x = x + self.size;
self.data[x] = v;
x >>= 1;
while x > 0 {
self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
x >>= 1;
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.n);
if l == r {
return self.e.clone();
}
let mut l = self.size + l;
let mut r = self.size + r;
let mut x = self.e.clone();
let mut y = self.e.clone();
while l < r {
if l & 1 == 1 {
x = (self.op)(&x, &self.data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
y = (self.op)(&self.data[r], &y);
}
l >>= 1;
r >>= 1;
}
(self.op)(&x, &y)
}
pub fn max_right<P>(&self, l: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(l <= self.n);
assert!(f(&self.e));
if l == self.n {
return self.n;
}
let mut l = l + self.size;
let mut sum = self.e.clone();
while {
l >>= l.trailing_zeros();
let v = (self.op)(&sum, &self.data[l]);
if !f(&v) {
while l < self.size {
l <<= 1;
let v = (self.op)(&sum, &self.data[l]);
if f(&v) {
sum = v;
l += 1;
}
}
return l - self.size;
}
sum = v;
l += 1;
l.count_ones() > 1
} {}
self.n
}
pub fn min_left<P>(&self, r: usize, f: P) -> usize
where
P: Fn(&T) -> bool,
{
assert!(r <= self.n);
assert!(f(&self.e));
if r == 0 {
return 0;
}
let mut r = r + self.size;
let mut sum = self.e.clone();
while {
r -= 1;
while r > 1 && r & 1 == 1 {
r >>= 1;
}
let v = (self.op)(&self.data[r], &sum);
if !f(&v) {
while r < self.size {
r = 2 * r + 1;
let v = (self.op)(&self.data[r], &sum);
if f(&v) {
sum = v;
r -= 1;
}
}
return r + 1 - self.size;
}
sum = v;
(r & (!r + 1)) != r
} {}
0
}
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin recurse ----------
// reference
// https://twitter.com/noshi91/status/1393952665566994434
// https://twitter.com/shino16_cp/status/1393933468082397190
pub fn recurse<A, R, F>(f: F) -> impl Fn(A) -> R
where
F: Fn(&dyn Fn(A) -> R, A) -> R,
{
fn call<A, R, F>(f: &F, a: A) -> R
where
F: Fn(&dyn Fn(A) -> R, A) -> R,
{
f(&|a| call(f, a), a)
}
move |a| call(&f, a)
}
// ---------- end recurse ----------