結果
| 問題 | No.3586 Divide and Be Conquered |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-22 11:38:47 |
| 言語 | Fix (1.6.1 + cp-library + minilib) |
| 結果 |
MLE
不安定
|
| 実行時間 | - |
| コード長 | 4,775 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
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()
);