Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ac38
let (&) = (@@)
module Array = struct
include Array
let fold_lefti f st a =
let st = ref st in
Array.iteri (fun i a -> st := f !st i a) a;
!st
end
let memoize_rec f =
let cache = Hashtbl.create 101 in
let rec g v =
try Hashtbl.find cache v with Not_found ->
let r = f g v in
Hashtbl.replace cache v r;
r
in
g
module IntIntervalSet = struct
module Set = Set.Make(struct
type t = int * int (* [a,b) *)
let compare (a1,a2 : t) (b1,b2) =
if a2 <= b1 then -1
else if b2 <= a1 then 1
else 0
end)
let find_opt e t = try Some (Set.find e t) with Not_found -> None
let rec add (a1,a2 as a) t =
assert (a1 < a2);
match find_opt (a1-1,a1) t with
| Some (b1,b2 as b) ->
let t = Set.remove b t in
add (min a1 b1, max a2 b2) t
| None ->
match find_opt (a2,a2+1) t with
| Some (b1,b2 as b) ->
let t = Set.remove b t in
add (min a1 b1, max a2 b2) t
| None ->
(* no overwrap found *)
Set.add a t
let min_elt = Set.min_elt
let remove = Set.remove
let empty = Set.empty
let cardinal = Set.cardinal
let is_empty = Set.is_empty
let print ppf t = Set.iter (fun (a1,a2) ->
Format.fprintf ppf "[%d,%d) " a1 a2) t;
Format.eprintf "@."
end
module IIS = IntIntervalSet
let input () =
let n = int_of_string & read_line () in
let cas =
Array.init (n-1) & fun _ ->
Scanf.sscanf (read_line ()) "%d %d" & fun c a -> c, a
in
n, cas
(* for test *)
let random size =
size,
Array.init (size - 1) (fun i ->
Random.int (i+1) + 1,
Random.int 1000000000)
let solve (n, cas) =
let grundy = memoize_rec & fun grundy -> function
| -1 -> 0
| i ->
let ci, _ = Array.unsafe_get cas i in
(*
assert (i-ci<=i-1);
assert (i-ci>=(-1));
*)
let rec loop j st =
if j = i then st
else
let g = grundy j in
loop (j+1) & IIS.add (g,g+1) st
in
let iiset = loop (i-ci) IIS.empty in
let search iiset =
if IIS.is_empty iiset then 0
else match IIS.min_elt iiset with
| (0,a2) -> a2
| (a1, _) -> 0
in
search iiset
in
let the_magic = Array.fold_lefti (fun st i (_,a) ->
if a mod 2 = 0 then st
else st lxor (grundy i)) 0 cas
in
print_endline & match the_magic with
| 0 -> "Second"
| _ -> "First"
let () = solve & input ()
(*
let () = solve & random 100000
*)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.