結果
| 問題 | No.3586 Divide and Be Conquered |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-22 15:34:22 |
| 言語 | Fix (1.6.1 + cp-library + minilib) |
| 結果 |
AC
不安定
|
| 実行時間 | 9 ms / 2,000 ms |
| + 107µs | |
| コード長 | 2,664 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
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()
);