結果

問題 No.3258 Xor Division Game
ユーザー koba-e964
提出日時 2025-10-17 12:50:07
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,777 bytes
コンパイル時間 12,844 ms
コンパイル使用メモリ 402,460 KB
実行使用メモリ 9,104 KB
最終ジャッジ日時 2025-10-17 12:50:44
合計ジャッジ時間 24,763 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 1 -- * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: field `freq` is never read
  --> src/main.rs:13:5
   |
10 | struct Stat<'a> {
   |        ---- field in this struct
...
13 |     freq: HashMap<u32, i32>,
   |     ^^^^
   |
   = note: `Stat` has a derived impl for the trait `Debug`, but this is intentionally ignored during dead code analysis
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use std::collections::*;

fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).unwrap();
    ret
}

#[derive(Debug)]
struct Stat<'a> {
    a: &'a [u32],
    unique: BTreeSet<usize>, // index
    freq: HashMap<u32, i32>,
}

fn facil(a: &[u32]) -> Stat<'_> {
    let mut freq = HashMap::new();
    for &f in a {
        *freq.entry(f).or_insert(0) += 1;
    }
    let stat = Stat {
        a: &a,
        unique: {
            let mut x = BTreeSet::new();
            for i in 0..a.len() {
                if freq[&a[i]] == 1 {
                    x.insert(i);
                }
            }
            x
        },
        freq,
    };
    stat
}

fn rec(s: Stat) -> i32 {
    let n = s.a.len();
    let mut seen = 0;
    let mut ans = 0;
    for &idx in &s.unique {
        // TODO: O(n^2)
        let t = facil(&s.a[seen..idx]);
        ans += rec(t) + 1;
        seen = idx + 1;
    }
    if seen > 0 && seen < n {
        let t = facil(&s.a[seen..]);
        ans += rec(t);
    }
    // eprintln!("stat = {s:?}, ans = {ans}");
    ans
}

// https://yukicoder.me/problems/no/3258 (3.5)
fn main() {
    getline();
    let f = getline().trim().split_whitespace()
        .map(|x| x.parse::<u32>().unwrap())
        .collect::<Vec<_>>();
    let n = f.len();
    let mut freq = HashMap::new();
    for &f in &f {
        *freq.entry(f).or_insert(0) += 1;
    }
    let stat = Stat {
        a: &f,
        unique: {
            let mut x = BTreeSet::new();
            for i in 0..n {
                if freq[&f[i]] == 1 {
                    x.insert(i);
                }
            }
            x
        },
        freq,
    };
    println!("{}", if rec(stat) % 2 == 1 {
        "Alice"
    } else {
        "Bob"
    });
}
0