ac38

gistfile1.ml

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
*)