結果

問題 No.3586 Divide and Be Conquered
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-22 15:34:22
言語 Fix
(1.6.1 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
AC  
実行時間 9 ms / 2,000 ms
+ 107µs
コード長 2,664 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,599 ms
コンパイル使用メモリ 251,428 KB
実行使用メモリ 9,856 KB
最終ジャッジ日時 2026-11-22 15:34:31
合計ジャッジ時間 8,351 ms
ジャッジサーバーID
(参考情報)
judge5_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

module Main;

import CPLib.IO;
import Hash::{combine_hash, Hash, Hash::hash};
import HashMap;

// import BinaryHeap;
// import BoolArray;
// import CPLib.Arithmetic;
// import CPLib.Bipartite;
// import CPLib.Bits;
// import CPLib.Convolution;
// import CPLib.DSegtree;
// import CPLib.Graph;
// import CPLib.LDSegtree;
// import CPLib.LSegtree;
// import CPLib.MaxFlow;
// import CPLib.Memoize;
// import CPLib.MinCostFlow;
// import CPLib.Misc;
// import CPLib.Monoid;
// import CPLib.Segtree;
// import CPLib.String;
// import CPLib.Trait;
// import CPLib.TwoSat;
// import CPLib.UnionFind;
// import CPLib.ZP;
import HashSet;

type State = struct {
    teban : I64,
};

impl State : Hash {
    hash : Main::State -> Std::U64 = |state| (
        state.@teban.hash
    );
}

impl State : Eq {
    eq : Main::State -> Main::State -> Std::Bool = |lhs, rhs| (
        lhs.@teban == rhs.@teban
    );
}

// move : State -> Array State = |s| (
//     let n = s.@teban;
//     if n == 1 { [] };
//     let gs = range(1, n/2+1).fold([], |m, gs|
//         
//     );
// );

grundy : I64 -> HashMap I64 I64 -> (I64, HashMap I64 I64) = |n, memo| (
    match memo.find(n) {
        some(g) => (g, memo),
        none() => (
            if n == 1 { (0, memo) };
            let (gss, memo) = range(1, n/2+1).fold(([], memo), |m, (gss, memo)|
                let a = m; let b = n - m;
                let gs = HashSet::empty(2);
                let (ga, memo) = grundy(a, memo);
                let (gb, memo) = grundy(b, memo);
                let gs = gs.HashSet::insert(ga).HashSet::insert(gb);
                let gss = gss.push_back(gs);
                (gss, memo)
            );
            let mex = count_up(0).filter(|g|
                gss.to_iter.check_any(|gs| !gs.contains(g))
            ).get_first.as_some;
            let memo = memo.insert(n, mex);
            (mex, memo)
        ),
    }
);

main : IO () = (
    let calc_g : I64 -> I64 = |n| (
        if n == 2 { 1 };
        if n == 3 { 2 };
        if n <= 6 { 0 };
        let m = n % 5;
        if m == 2 { 1 };
        if m == 3 { 1 };
        0
    );
    // let memo = HashMap::empty(1e5);
    // let memo = *range(1, 1e2+1).fold_m(memo, |n, memo|
    //     let (g, memo) = grundy(n, memo);
    //     // "g({}) = {}".eprintfln((n, g,));;
    //     assert_eq(|_|"g != calc_g", g, calc_g(n));;
    //     memo.pure
    // );
    let t = *read_i;
    range(0, t).fold_m((), |_, _|
        let n = *read_i;
        let as = *read_is(n);
        let g = as.to_iter.map(calc_g).fold(0, bit_xor);
        let ans = if g != 0 { "First" } else { "Second" };
        ans.println
    );;
    pure()
);
0