結果

問題 No.2745 String Swap Battle
ユーザー xsdxsd
提出日時 2024-04-21 12:01:34
言語 OCaml
(5.1.0)
結果
WA  
実行時間 -
コード長 2,427 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 22,272 KB
実行使用メモリ 20,784 KB
最終ジャッジ日時 2024-10-13 10:24:46
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 250 ms
14,004 KB
testcase_01 AC 252 ms
13,876 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 4 ms
6,816 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 WA -
testcase_07 AC 556 ms
20,496 KB
testcase_08 AC 556 ms
20,524 KB
testcase_09 AC 489 ms
18,772 KB
testcase_10 AC 206 ms
13,568 KB
testcase_11 AC 97 ms
11,168 KB
testcase_12 AC 181 ms
11,392 KB
testcase_13 AC 176 ms
11,392 KB
testcase_14 AC 177 ms
11,392 KB
testcase_15 AC 95 ms
7,552 KB
testcase_16 AC 93 ms
7,680 KB
testcase_17 AC 93 ms
7,552 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 2 ms
6,820 KB
testcase_20 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

Scanf.scanf "%d" (fun n ->
    let module S = Set.Make (struct type t = int let compare = compare end) in
    let calc_cost s limit =
        let len = String.length s in
        let pos = Array.make 26 S.empty in
        let arena = Array.make len 0 in
        String.iteri (fun i c ->
            let a = int_of_char c - 97 in
            pos.(a) <- S.add i pos.(a);
            arena.(i) <- a) s;
        let rec loop i cur count =
            if i = len then count else
            if count = limit then count else
            if arena.(i) = cur then
                let () = pos.(cur) <- S.remove i pos.(cur) in
                loop (i + 1) cur count else
            if S.is_empty pos.(cur) then loop i (cur + 1) count else
                let mp = S.max_elt pos.(cur) in
                let () =
                    let q = arena.(i) in
                    pos.(cur) <- S.remove mp pos.(cur);
                    pos.(q) <- S.add mp (S.remove i pos.(q));
                    arena.(i) <- cur;
                    arena.(mp) <- q
                in
                loop (i + 1) cur (count + 1)
        in
        let count = loop 0 0 0 in
        let check arena =
            let rec loop i =
                if i = len - 1 then false else
                    if arena.(i) = arena.(i + 1) then true else loop (i + 1)
            in
            loop 0
        in
        let count = if limit = max_int then (
            if count = 0 then (if check arena then 1 else 2) else count
        ) else (
            if (limit - count) mod 2 = 0 then count else (
               if check arena then limit else (
                    let c = arena.(len - 1) in
                    arena.(len - 1) <- arena.(len - 2);
                    arena.(len - 2) <- c;
                    limit
                )
            )
        )
        in
        let ret = String.init len (fun i -> char_of_int (97 + arena.(i))) in
        count, ret
    in
    let s = Array.init n (fun _ -> Scanf.scanf " %s" (fun s -> s)) in
    let k = Array.fold_left (fun acc s -> min acc (fst (calc_cost s max_int))) max_int s in
(*    let k = 1 in *)
    let s2 = Array.map (fun s -> snd (calc_cost s k)) s in

    let s3 = Array.copy s2 in
    Array.sort compare s3;
    let winner = Array.fold_left (fun acc v -> if v = s3.(0) then acc + 1 else acc) 0 s2 in
    Array.iter (fun v -> Printf.printf "%d\n" @@ if v = s3.(0) then n + 1 - winner else 0) s2;
)
0