結果

問題 No.3586 Divide and Be Conquered
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-21 20:48:05
言語 Fix
(1.6.1 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,311 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,748 ms
コンパイル使用メモリ 249,000 KB
実行使用メモリ 9,908 KB
最終ジャッジ日時 2026-11-21 20:48:17
合計ジャッジ時間 8,385 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 11
権限があれば一括ダウンロードができます

ソースコード

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 = union {
    teban : I64,
    split : I64,
    choice : (I64, I64)
};

impl State : Hash {
    hash : Main::State -> Std::U64 = |state| (
        match state {
            teban(n) => (
                combine_hash(0.u64, n.hash)
            ),
            split(n) => (
                combine_hash(1.u64, n.hash)
            ),
            choice((n, m)) => (
                combine_hash(n.u64, m.u64).combine_hash(2.u64)
            )
        }
    );
}

impl State : Eq {
    eq : Main::State -> Main::State -> Std::Bool = |lhs, rhs| (
        match lhs {
            teban(n) => (
                rhs.is_teban && n == rhs.as_teban
            ),
            split(n) => (
                rhs.is_split && n == rhs.as_split
            ),
            choice((n, m)) => (
                rhs.is_choice && (n, m) == rhs.as_choice
            )
        }
    );
}

transit : State -> Array State = |s| (
    match s {
        teban(n) => (
            if n == 1 { [] };
            [split(n)]
        ),
        split(n) => (
            range(1, n/2+1).fold([], |m, states|
                let s = choice((m, n-m));
                states.push_back(s)
            )
        ),
        choice((n, m)) => (
            if n == m {
                [teban(n)]
            } else {
                [teban(n), teban(m)]
            }
        ),
    }
);

grundy : State -> HashMap State I64 -> (I64, HashMap State I64) = |state, memo| (
    match memo.find(state) {
        some(g) => (g, memo),
        none() => (
            let nexts = transit(state);
            let (gs, memo) = nexts.to_iter.fold((HashSet::empty(nexts.@size), memo), |next, (gs, memo)|
                let (g, memo) = grundy(next, memo);
                let gs = gs.HashSet::insert(g);
                (gs, memo)
            );
            let mex = count_up(0).filter(|n| !gs.contains(n)).get_first.as_some;
            let memo = memo.insert(state, mex);
            (mex, memo)
        ),
    }
);

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