Submission #1678342
Source Code Expand
(** val add : int -> int -> int **) let rec add = ( + ) (** val sub : int -> int -> int **) let rec sub = ( - ) module Nat = struct (** val div2 : int -> int **) let rec div2 = (fun x -> x / 2) end (** val lower_bound_aux : (int -> bool) -> int -> int -> int **) let rec lower_bound_aux p_dec x x0 = (fun fO fS n -> if n = 0 then fO () else fS (n-1)) (fun _ -> x) (fun n0 -> if p_dec (add x (Nat.div2 (succ n0))) then lower_bound_aux p_dec x (Nat.div2 (succ n0)) else lower_bound_aux p_dec (add (succ (Nat.div2 (succ n0))) x) (sub (succ n0) (succ (Nat.div2 (succ n0))))) x0 (** val lower_bound : (int -> bool) -> int -> int -> int **) let lower_bound p_dec alpha beta = lower_bound_aux p_dec alpha (sub beta alpha) let () = let n = Scanf.scanf "%d\n" (fun n -> n) in let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in Array.sort compare as_; Printf.printf "%d\n" (n - lower_bound (fun i -> Array.fold_left (fun (j, (acc, b)) a -> (j + 1, if i = j then (acc, b) else (acc + a, b && a <= 2 * acc)) ) (0, (as_.(i), true)) as_ |> snd |> snd) 0 n)
Submission Info
Submission Time | |
---|---|
Task | B - Colorful Creatures |
User | fetburner |
Language | OCaml (4.02.3) |
Score | 400 |
Code Size | 1214 Byte |
Status | AC |
Exec Time | 91 ms |
Memory | 4736 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 91 ms | 3456 KB |
in10.txt | AC | 34 ms | 2944 KB |
in11.txt | AC | 87 ms | 3456 KB |
in12.txt | AC | 88 ms | 3456 KB |
in13.txt | AC | 89 ms | 4736 KB |
in2.txt | AC | 89 ms | 3456 KB |
in3.txt | AC | 89 ms | 3456 KB |
in4.txt | AC | 89 ms | 3456 KB |
in5.txt | AC | 34 ms | 2944 KB |
in6.txt | AC | 84 ms | 3456 KB |
in7.txt | AC | 89 ms | 3456 KB |
in8.txt | AC | 83 ms | 3456 KB |
in9.txt | AC | 12 ms | 2688 KB |
sample1.txt | AC | 1 ms | 384 KB |
sample2.txt | AC | 1 ms | 384 KB |
sample3.txt | AC | 1 ms | 384 KB |