結果

問題 No.9 モンスターのレベル上げ
コンテスト
ユーザー penqen
提出日時 2021-03-29 01:58:14
言語 Elixir
(1.18.1)
結果
MLE  
実行時間 -
コード長 3,402 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 65,272 KB
実行使用メモリ 646,244 KB
最終ジャッジ日時 2024-12-31 05:44:24
合計ジャッジ時間 55,630 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 MLE * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
    warning: use Bitwise is deprecated. import Bitwise instead
    │
  2 │   use Bitwise
    │   ~~~~~~~~~~~
    │
    └─ Main.exs:2: Main (module)

ソースコード

diff # 

defmodule Main do
  use Bitwise
  defmodule Heap do
    defstruct data: nil, size: 0, comparator: nil
    def new(comparator), do: %__MODULE__{comparator: comparator}
    def empty?(%__MODULE__{data: nil, size: 0}), do: true
    def empty?(%__MODULE__{}), do: false 
    def size(%__MODULE__{size: size}), do: size
    def top(%__MODULE__{data: nil}), do: nil
    def top(%__MODULE__{data: {v, _}}), do: v
    def pop(%__MODULE__{data: nil, size: 0} = heap), do: heap
    def pop(%__MODULE__{data: {_v, queue}, size: n, comparator: comp} = heap),
      do: %{heap | data: dequeue(queue, comp), size: n - 1}
    def pop!(%__MODULE__{} = heap), do: {Heap.top(heap), Heap.pop(heap)}
    def push(%__MODULE__{data: h, size: n, comparator: comp} = heap, v),
      do: %{heap | data: meld(h, {v, nil}, comp), size: n + 1}
    defp meld(nil, v, _comp), do: v
    defp meld(v, nil, _comp), do: v
    defp meld({v0, q0} = left , {v1, q1} = right, comp) do
      if comp.(v0, v1), do: {v0, enqueue(q0, right)}, else: {v1, enqueue(q1, left)}
    end
    defp enqueue(q, v)
    defp enqueue(nil, v), do: [v]
    defp enqueue(q, v), do: [v | q]
    defp dequeue(nil, _), do: nil
    defp dequeue([], _), do: nil
    defp dequeue([q], _), do: q
    defp dequeue([q0, q1 | q], comp), do: meld(meld(q0, q1, comp), dequeue(q, comp), comp)
    defimpl Collectable do
      def into(heap) do
        {
          heap,
          fn
            heap, {:cont, v} -> Heap.push(heap, v)
            heap, :done -> heap
            _heap, :halt -> :ok
          end
        }
      end
    end
    defimpl Enumerable do
      def count(heap), do: {:ok, Heap.size(heap)}
      def member?(_, _), do: {:error, __MODULE__}
      def slice(_), do: {:error, __MODULE__}
      def reduce(_heap, {:halt, acc}, _fun), do: {:halted, acc}
      def reduce(heap, {:suspend, acc}, fun), do: {:suspended, acc, &reduce(heap, &1, fun)}
      def reduce(%Heap{data: nil, size: 0}, {:cont, acc}, _fun), do: {:done, acc}
      def reduce(heap, {:cont, acc}, fun) do
        reduce(Heap.pop(heap), fun.(Heap.top(heap), acc), fun)
      end
    end
  end

  def main do
    n = IO.read(:line)
    an = IO.read(:line)
    bn = IO.read(:line)
    current = self()
    n = spawn_link(fn -> send(current, {self(), n |> String.trim() |> String.to_integer()}) end)
    an = spawn_link(fn -> send(current, {self(), an |> String.trim() |> String.split(" ") |> Enum.map(&(String.to_integer(&1) <<< 12)) |> Enum.into(Heap.new(fn l, r -> l < r end)) }) end)
    bn = spawn_link(fn -> send(current, {self(), bn |> String.trim() |> String.split(" ") |> Enum.map(&(div(String.to_integer(&1), 2) <<< 12)) }) end) 
    n = receive do {^n, v} -> v end
    heap = receive do {^an, v} -> v end
    bn = receive do {^bn, v} -> v end
    for i <- 0..(n-1) do
      spawn_link(fn ->
        {bn1, bn0} = Enum.split(bn, i)
        send(current, {self(), fight(heap, bn0, bn1)})
      end)
    end
    |> Enum.reduce(:infinity, fn pid, min ->
      receive do
        {^pid, times} -> if min > times, do: times, else: min
      end
    end)
    |> IO.puts
  end 

  def fight(heap, bn0, bn1)
  def fight(heap, [], []), do: heap |> Enum.max_by(fn v -> v &&& 0xFFF end) |> Bitwise.&&&(0xFFF)
  def fight(heap, [], bn), do: fight(heap, bn, [])
  def fight(heap, [b | tail], bn) do
    {a, heap} = Heap.pop!(heap)
    heap |> Heap.push(a + b + 1) |> fight(tail, bn)
  end
end
0