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