結果

問題 No.3586 Divide and Be Conquered
コンテスト
ユーザー 👑 tttmmmyyyy
提出日時 2026-11-22 11:38:47
言語 Fix
(1.6.1 + cp-library + minilib)
コンパイル:
fix_c _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 4,775 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,058 ms
コンパイル使用メモリ 283,120 KB
実行使用メモリ 1,144,116 KB
最終ジャッジ日時 2026-11-22 11:39:02
合計ジャッジ時間 14,311 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 6 MLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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 : Array I64,
    split : (Array I64, I64),
    choice : (Array I64, 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((ns, n, m)) => (
                combine_hash(2.u64, (ns, (n, m)).hash)
            )
        }
    );
}

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

remove : I64 -> Array a -> Array a = |i, xs| (
    xs.get_sub(0, i) + xs.get_sub(i+1, xs.@size)
);

move : State -> Array State = |s| (
    match s {
        teban(ns) => (
            range(0, ns.@size).map(|i|
                let n = ns[i].iget;
                let ns = ns.remove(i);
                State::split((ns, n))
            ).to_array
        ),
        split((ns, n)) => (
            range(1, n/2+1).fold([], |m, states|
                let s = choice((ns, m, n-m));
                states.push_back(s)
            )
        ),
        choice((ns, n, m)) => (
            let insert = |n, ns : Array _| (
                if n == 1 { ns };
                ns.push_back(n).sort
            );
            if n == m {
                [teban(ns.insert(n))]
            } else {
                [teban(ns.insert(n)), teban(ns.insert(m))]
            }
        ),
    }
);

// grundy : State -> HashMap State I64 -> (I64, HashMap State I64) = |state, memo| (
//     match memo.find(state) {
//         some(g) => (g, memo),
//         none() => (
//             let nexts = state.move;
//             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)
//         ),
//     }
// );

wins : State -> HashMap State Bool -> (Bool, HashMap State Bool) = |state, memo| (
    match memo.find(state) {
        some(g) => (g, memo),
        none() => (
            let nexts = state.move;
            let (any_loose, memo) = nexts.to_iter.loop_iter((false, memo), |next, (any_loose, memo)|
                let (wins, memo) = wins(next, memo);
                let any_loose = any_loose || !wins;
                if any_loose { (true, memo).break };
                (any_loose, memo).continue
            );
            let wins = any_loose;
            let memo = memo.insert(state, wins);
            (wins, memo)
        ),
    }
);

main : IO () = (
    // let calc_g : I64 -> I64 = |n| (
    //     let m = n % 5;
    //     if m == 2 { 1 };
    //     if m == 3 { 2 };
    //     0
    // );
    // let memo = *range(1, 3e1+1).fold_m(memo, |n, memo|
    //     let memo = *range(1, 3e1+1).fold_m(memo, |m, memo|
    //         let (g, memo) = grundy(teban([3, n, m]), memo);
    //         // "g([{}, {}]) = {}, ".eprintf((n.right_aligned_to(2), m.right_aligned_to(2), g));;
    //         "{}, ".eprintf((if g == 0 { "S" } else { " " }, ));;
    //         memo.pure
    //     );
    //     "".eprintfln(());;
    //     memo.pure
    // );
    let t = *read_i;
    let memo = HashMap::empty(1e5);
    range(0, t).fold_m(memo, |_, memo|
        let n = *read_i;
        let as = *read_is(n);
        let as = as.to_iter.map(|n|
            if n >= 4 { (n-4) % 5 + 4 } else { n }
        ).filter(|n| n != 1).to_array;
        let (wins, memo) = wins(teban(as), memo);
        let ans = if wins { "First" } else { "Second" };
        ans.println;;
        memo.pure
    );;
    pure()
);
0