Submission #434063

---

Source Code Expand

let calc a b arr =
  let (ba,ca) = arr in
  let rec inner1 pos pa pb = 
    if pos=6 then (pa,pb)
    else
      let i = 1 lsl pos in
      let j = 1 lsl (pos+3) in
      let x = pos/3 in
      let y = pos mod 3 in
        if ((a land i)>0 && (a land j) > 0) || ((b land i)>0 && (b land j) > 0)  then
          inner1 (pos+1) (pa+ba.(x).(y)) pb
        else
          inner1 (pos+1) pa (pb+ba.(x).(y))
  in
  let rec inner2 pos pa pb = 
    if pos=9 then (pa,pb)
    else if pos mod 3 = 2 then 
      inner2 (pos+1) pa pb
    else
      let i = 1 lsl pos in
      let j = 1 lsl (pos+1) in
      let x = pos/3 in
      let y = pos mod 3 in
        if ((a land i)>0 && (a land j) > 0) || ((b land i)>0 && (b land j) > 0)  then
          inner2 (pos+1) (pa+ca.(x).(y)) pb
        else
          inner2 (pos+1) pa (pb+ca.(x).(y))
  in
  let (ta,tb) = inner1 0 0 0 in
    inner2 0 ta tb in 

let rec max_search a b arr memo =
  if not (memo.(a).(b) = (-1,-1)) then
    (memo.(a).(b))
  else if a lor b = (1 lsl 9)-1 then 
    let (pa,pb) = calc a b arr in
      Array.set memo.(a) b (pa,pb); (pa,pb)
  else
    let ans = ref (-1,-1) in
      for i = 0 to 8 do
        if ((a land (1 lsl i))=0) && ((b land (1 lsl i))=0) then
          let (pa,pb) = min_search (a lor (1 lsl i)) b arr memo in
          let (ta,_) = !ans in
            if pa > ta then ans := (pa,pb) else ()
        else ()
      done;
      Array.set memo.(a) b !ans;!ans
and min_search a b arr memo =
  if not (memo.(a).(b) = (-1,-1)) then
    (memo.(a).(b))
  else if a lor b = (1 lsl 9)-1 then 
    let (pa,pb) = calc a b arr in
      Array.set memo.(a) b (pa,pb); (pa,pb)
  else
    let ans = ref (-1,-1) in
      for i = 0 to 8 do
        if ((a land (1 lsl i))=0) && ((b land (1 lsl i))=0) then
          let (pa,pb) = max_search a (b lor (1 lsl i)) arr memo in
          let (_,tb) = !ans in
            if pb > tb then ans := (pa,pb) else ()
        else ()
      done;
      Array.set memo.(a) b !ans;!ans
  in
let ba = Array.make_matrix 2 3 0 in
let ca = Array.make_matrix 3 2 0 in
  for i = 0 to 1 do
    Scanf.scanf "%d %d %d\n" 
      (fun x y z -> Array.set ba.(i) 0 x; Array.set ba.(i) 1 y; Array.set ba.(i) 2 z)
  done;
  for i = 0 to 2 do
    Scanf.scanf "%d %d\n" 
      (fun x y -> Array.set ca.(i) 0 x; Array.set ca.(i) 1 y)
  done;
  (* print_endline "java"; *)
  let (ra,rb) = max_search 0 0 (ba,ca) (Array.make_matrix (1 lsl 9) (1 lsl 9) (-1,-1)) in
    Printf.printf "%d\n%d\n" ra rb

Submission Info

Judge Result