#1171052 (Rust) No.3586 Divide and Be Conquered

• 問題: No.3586 Divide and Be Conquered
• ユーザー: akakimidori
• 提出日時: 2026-07-10 23:18:31
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 161 ms / 2,000 ms
• コード長: 3,842 bytes
• コンパイル時間: 11,223 ms
• コンパイル使用メモリ: 187,324 KB
• 実行使用メモリ: 7,424 KB
• 最終ジャッジ日時: 2026-07-10 23:18:45
• 合計ジャッジ時間: 10,492 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 19

コンパイルメッセージ

warning: function `test` is never used
  --> src/main.rs:22:4
   |
22 | fn test() {
   |    ^^^^
   |
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: function `naive` is never used
  --> src/main.rs:56:4
   |
56 | fn naive(mut a: Vec<usize>, map: &mut Map<Vec<usize>, bool>) -> bool {
   |    ^^^^^

warning: type alias `Map` is never used
   --> src/main.rs:111:6
    |
111 | type Map<K, V> = BTreeMap<K, V>;
    |      ^^^

warning: type alias `Set` is never used
   --> src/main.rs:112:6
    |
112 | type Set<T> = BTreeSet<T>;
    |      ^^^

warning: type alias `Deque` is never used
   --> src/main.rs:113:6
    |
113 | type Deque<T> = VecDeque<T>;
    |      ^^^^^

warning: function `rand_memory` is never used
   --> src/main.rs:124:4
    |
124 | fn rand_memory() -> usize {
    |    ^^^^^^^^^^^

warning: function `rand` is never used
   --> src/main.rs:128:4
    |
128 | fn rand() -> usize {
    |    ^^^^

warning: function `shuffle` is never used
   --> src/main.rs:141:4
    |
141 | fn shuffle<T>(a: &mut [T]) {
    |    ^^^^^^^

ソースコード

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    //test();
    let t: u32 = sc.next();
    for _ in 0..t {
        let n = sc.next::<usize>();
        let a = sc.next_vec::<usize>(n);
        if fast(a) {
            writeln!(out, "First").ok();
        } else {
            writeln!(out, "Second").ok();
        }
    }
}

// 実験しても何も見えん
// mod 5?
// 0, 1, 4: lose
// 2, 3: win
//
//

fn test() {
    let mut map = Map::new();
    println!("{:?}", naive(vec![1], &mut map));
    println!("{:?}", naive(vec![2], &mut map));
    println!("{:?}", naive(vec![4], &mut map));
    println!("{:?}", naive(vec![2, 3, 7], &mut map));
    let mut set = Set::new();
    for _ in 0..10000 {
        let n = rand() % 3 + 1;
        let mut a = (0..n).map(|_| rand() % 10 + 2).collect::<Vec<_>>();
        a.sort();
        if set.insert(a.clone()) {
            let res = naive(a.clone(), &mut map);
            assert_eq!(res, fast(a.clone()), "{:?}", a);
            let cnt = a.iter().filter(|a| **a % 5 == 2 || **a % 5 == 3).count();
            if cnt % 2 == 1 {
                assert!(res, "{:?}", a);
            } else if res {
                println!("{:?}: {} {}", a, res, cnt);
            }
        }
    }
    for i in 1..40 {
        println!("{}: {}", i, naive(vec![i], &mut map));
    }
}

fn fast(a: Vec<usize>) -> bool {
    let c = a.iter().filter(|a| **a % 5 == 3).count();
    let d = a.iter().filter(|a| **a % 5 == 2).count();
    let e = a.iter().filter(|a| **a == 3).count();
    (c + d) % 2 == 1 || e % 2 == 1
}

fn naive(mut a: Vec<usize>, map: &mut Map<Vec<usize>, bool>) -> bool {
    a.sort();
    a.retain(|a| *a > 1);
    if a.is_empty() {
        return false;
    }
    let a = a;
    let res = (0..a.len()).any(|i| {
        let mut a = a.clone();
        let v = a.remove(i);
        let a = a;
        (1..v).all(|j| {
            let mut b = a.clone();
            let mut c = a.clone();
            b.push(j);
            c.push(v - j);
            !naive(b, map) || !naive(c, map)
        })
    });
    map.insert(a, res);
    res
}

// ---------- 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);
}
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}