結果

問題 No.3258 Xor Division Game
ユーザー koba-e964
提出日時 2025-10-17 16:36:57
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,859 bytes
コンパイル時間 11,101 ms
コンパイル使用メモリ 405,008 KB
実行使用メモリ 380,852 KB
最終ジャッジ日時 2025-10-17 16:37:19
合計ジャッジ時間 19,647 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 1 -- * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `n`
  --> src/main.rs:41:9
   |
41 |     let n = a.len();
   |         ^ help: if this is intentional, prefix it with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: field `freq` is never read
  --> src/main.rs:14:5
   |
10 | struct Stat {
   |        ---- field in this struct
...
14 |     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 {
    l: usize,
    r: usize,
    unique: BTreeSet<usize>, // index
    freq: HashMap<u32, i32>,
}

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

fn rec(a: &[u32], s: Stat) -> i32 {
    let n = a.len();
    let mut seen = s.l;
    let mut ans = 0;
    for &idx in &s.unique {
        // TODO: O(n^2)
        let t = facil(&a, seen, idx);
        ans += rec(a, t) + 1;
        seen = idx + 1;
    }
    if seen > s.l && seen < s.r {
        let t = facil(&a, seen, s.r);
        ans += rec(a, 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 {
        l: 0,
        r: n,
        unique: {
            let mut x = BTreeSet::new();
            for i in 0..n {
                if freq[&f[i]] == 1 {
                    x.insert(i);
                }
            }
            x
        },
        freq,
    };
    println!("{}", if rec(&f, stat) % 2 == 1 {
        "Alice"
    } else {
        "Bob"
    });
}
0