Submission #3728792

---

Source Code Expand

module S =
  Set.Make (struct
      type t = int
      let compare = compare
    end)

let id x = x

let init n f =
  let rec loop i l = if i < n then loop (i + 1) (f i :: l) else l in
  List.rev (loop 0 [])

let rec is_sorted = function
    [] -> true
  | [_] -> true
  | x :: y :: l -> if compare x y <= 0 then is_sorted (y :: l) else false

let n = Scanf.scanf " %d" id
let m = Scanf.scanf " %d" id
let q = Scanf.scanf " %d" id
let a =
  init q (fun _ -> Scanf.scanf " %d" id)
  |> List.rev

let () =
  let cnt = Array.make (m + 1) 0 in
  let nxt = Array.make (m + 1) None in
  let root = ref (-1) in
  let f (cur, ts) a =
    if cnt.(a) > 0 then
      let nxt = match nxt.(a) with
          Some nxt -> nxt
        | None -> raise (Failure "") in
      let () = cnt.(a) <- cnt.(a) - 1;
               cnt.(nxt) <- cnt.(nxt) + 1 in
      (cur, ts)
    else
      match nxt.(a) with
        Some _ -> (cur, ts) (* do nothing *)
      | None -> match cur with
                  None -> let () = root := a;
                                   nxt.(a) <- Some 0;
                                   cnt.(a) <- cnt.(0);
                                   cnt.(0) <- 0 in
                          (Some a, S.remove a ts)
                | Some cur -> let () = nxt.(cur) <- Some a;
                                       nxt.(a) <- Some 0;
                                       cnt.(a) <- cnt.(0);
                                       cnt.(0) <- 0 in
                              (Some a, S.remove a ts) in
  let () = cnt.(0) <- n - 1 in
  let (_, ts) = List.fold_left f (None, S.of_list (init m (fun i -> i + 1))) a in
  let hs =
    let rec loop i f l =
      match nxt.(i) with
        None -> l
      | Some nxt -> if cnt.(i) > 0 || f then
                      loop nxt true (i :: l)
                    else
                      loop nxt f l in
    List.rev (loop !root false []) in
  let mx = List.fold_left max min_int hs in
  let mn = try S.min_elt ts with Not_found -> max_int in
  if is_sorted hs && mx <= mn then
    print_endline "Yes"
  else
    print_endline "No"

Submission Info

Judge Result