結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー elphe
提出日時 2025-10-25 11:26:28
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 4,207 bytes
コンパイル時間 15,628 ms
コンパイル使用メモリ 404,308 KB
実行使用メモリ 9,856 KB
最終ジャッジ日時 2025-11-01 09:59:09
合計ジャッジ時間 20,488 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

fn prepare(n: usize, s: &Vec<u8>) -> Vec<[i32; 2]> {
    let mut csum = vec![[0i32, 0i32]; n + 1];
    for i in 0..n {
        if s[i] == b'w' || s[i] == b'a' {
            csum[i + 1] = [csum[i][0], csum[i][1] + 1];
        } else {
            csum[i + 1] = [csum[i][0] + 1, csum[i][1]];
        }
    }
    csum
}

fn solve(
    n: usize,
    q: usize,
    s: &Vec<u8>,
    mut t: Vec<i64>,
    mut x: Vec<i64>,
    csum: &Vec<[i32; 2]>,
) -> String {
    let mut ans = vec![b'?'; q];

    for i in 0..q {
        x[i] -= 1; // 1-indexed -> 0-indexed
        if t[i] > 60 {
            t[i] = 60;
        }
        let ti = t[i] as u32;

        // mul as i128 to avoid intermediate overflow
        let mul = (5i128) * ((1i128) << ti) - 4i128;

        // binary search for maximum l in [0, n] satisfying
        // csum[l][0] + csum[l][1] * mul <= x[i]
        let mut l: isize = 0;
        let mut r: isize = (n as isize) + 1;
        while l + 1 < r {
            let mid = ((l + r) / 2) as usize;
            let cnt_a_w = csum[mid][1] as i128;
            let cnt_other = csum[mid][0] as i128;
            // first condition: cnt_a_w > (x - cnt_other) / mul
            let cond1 = if mul != 0 {
                // note: use floor div for negative safety though x - cnt_other is non-negative in valid ranges
                cnt_a_w > ((x[i] as i128 - cnt_other) / mul)
            } else {
                false
            };
            if cond1 {
                r = mid as isize;
            } else if cnt_other + cnt_a_w * mul > x[i] as i128 {
                r = mid as isize;
            } else {
                l = mid as isize;
            }
        }

        let l_usize = l as usize;
        let total_at_l = (csum[l_usize][0] as i128) + (csum[l_usize][1] as i128) * mul;
        if total_at_l == x[i] as i128 {
            // exact match
            // S[l]
            // safe because l in [0..=n-1] when match exists; but if l == n then S[n] would be OOB.
            // In C++ code it assumed valid; we mirror that assumption.
            ans[i] = s[l_usize];
        } else {
            x[i] -= total_at_l as i64;
            // target starts as S, but switch to literal strings when encountering a/w
            let mut target_bytes: &[u8] = s;
            let mut cursor: usize = l_usize;
            let mut remaining_t = t[i] - 1;
            while x[i] != 0 && remaining_t >= 0 {
                // current character at cursor in target_bytes
                let ch = *target_bytes.get(cursor).unwrap_or(&b'?');
                if ch == b'a' {
                    target_bytes = b"answer";
                } else if ch == b'w' {
                    target_bytes = b"warong";
                } else {
                    // abnormal; break
                    break;
                }

                cursor = 0;
                let mul2 = (5i128) * ((1i128) << (remaining_t as u32)) - 4i128;
                // iterate over target_bytes
                while x[i] != 0 {
                    let tch = *target_bytes.get(cursor).unwrap_or(&b'?');
                    if tch != b'w' && tch != b'a' {
                        x[i] -= 1;
                        cursor += 1;
                    } else if (x[i] as i128) < mul2 {
                        break;
                    } else {
                        x[i] -= mul2 as i64;
                        cursor += 1;
                    }
                    if cursor >= target_bytes.len() {
                        break;
                    }
                }

                remaining_t -= 1;
            }

            ans[i] = *target_bytes.get(cursor).unwrap_or(&b'?');
        }
    }

    // convert to String
    String::from_utf8(ans).unwrap_or_default()
}

fn main() {
    input! {
        n: usize,
        q: usize,
        s_raw: String,
        queries: [(i64, i64); q],
    }

    let s_bytes: Vec<u8> = s_raw.into_bytes();
    let mut t = vec![0i64; q];
    let mut x = vec![0i64; q];
    for i in 0..q {
        t[i] = queries[i].0;
        x[i] = queries[i].1;
    }

    let csum = prepare(n, &s_bytes);
    let ans = solve(n, q, &s_bytes, t, x, &csum);
    println!("{}", ans);
}
0