結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー elphe
提出日時 2025-11-23 15:37:55
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 2,586 bytes
コンパイル時間 12,562 ms
コンパイル使用メモリ 398,224 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2025-11-23 15:38:17
合計ジャッジ時間 21,009 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{fastout, input, marker::Bytes};

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        s: Bytes,
        queries: [(u64, u64); q],
    }

    println!("{}", output(solve(n, s, queries)));
}

fn prepare(n: usize, s: &[u8]) -> Vec<u32> {
    let mut count_until = Vec::with_capacity(n + 1);
    count_until.push(0);
    for s in s {
        let prev = *count_until.last().unwrap();
        match s {
            b'w' | b'a' => count_until.push(prev + 1),
            _ => count_until.push(prev),
        }
    }
    count_until
}

fn under_bound(n: usize, count_until: &[u32], t: u64, x: u64) -> usize {
    let mut l = 0;
    let mut r = n + 1;
    while l + 1 < r {
        let c = (l + r) / 2;
        if x < c as u64
            || (x - c as u64 + count_until[c] as u64) / ((5 << t) - 4) < count_until[c] as u64
            || x < count_until[c] as u64 * ((5 << t) - 5) + c as u64
        {
			r = c;
        } else {
            l = c;
        }
    }
    l
}

fn solve(n: usize, s: Vec<u8>, queries: Vec<(u64, u64)>) -> Vec<u8> {
    let count_until = prepare(n, &s);
    let mut ans = Vec::with_capacity(queries.len());
    for (mut t, mut x) in queries {
        let mut target = &s[..];
        let mut pos = 0;
        t = t.min(60);
        x -= 1;
        let skip = under_bound(n, &count_until, t, x);
        x -= skip as u64 + ((5 << t) - 5) * count_until[skip] as u64;
        pos += skip;

        const WARONG: [u8; 6] = [b'w', b'a', b'r', b'o', b'n', b'g'];
        const ANSWER: [u8; 6] = [b'a', b'n', b's', b'w', b'e', b'r'];
        while x != 0 {
            t -= 1;
            match target[pos] {
                b'w' => target = &WARONG,
                b'a' => target = &ANSWER,
                _ => (),
            }
            pos = 0;

            for s in target {
                if t == 0 {
                    x -= 1;
                } else {
                    match *s {
                        b'w' | b'a' => match x.cmp(&((5 << t) - 4 as u64)) {
                            std::cmp::Ordering::Less => break,
                            std::cmp::Ordering::Equal => x = 0,
                            std::cmp::Ordering::Greater => x -= (5 << t) - 4 as u64,
                        },
                        _ => x -= 1,
                    }
                }
                pos += 1;
                if x == 0 {
                    break;
                }
            }
        }
        ans.push(target[pos]);
    }
    ans
}

fn output(ans: Vec<u8>) -> String {
    String::from_utf8(ans).unwrap()
}
0