結果

問題 No.241 出席番号(1)
ユーザー hytkxdhytkxd
提出日時 2024-05-08 00:37:06
言語 Ruby
(3.3.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 1,351 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-05-08 00:37:11
合計ジャッジ時間 3,949 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
12,160 KB
testcase_01 AC 83 ms
12,160 KB
testcase_02 AC 88 ms
12,160 KB
testcase_03 AC 78 ms
12,416 KB
testcase_04 AC 79 ms
12,288 KB
testcase_05 AC 78 ms
12,416 KB
testcase_06 AC 80 ms
12,416 KB
testcase_07 AC 80 ms
12,288 KB
testcase_08 AC 80 ms
12,160 KB
testcase_09 AC 80 ms
12,288 KB
testcase_10 AC 91 ms
12,416 KB
testcase_11 AC 82 ms
12,160 KB
testcase_12 AC 78 ms
12,288 KB
testcase_13 AC 79 ms
12,160 KB
testcase_14 AC 82 ms
12,416 KB
testcase_15 AC 84 ms
12,160 KB
testcase_16 AC 80 ms
12,416 KB
testcase_17 AC 77 ms
12,288 KB
testcase_18 AC 82 ms
12,288 KB
testcase_19 AC 81 ms
12,160 KB
testcase_20 AC 79 ms
12,416 KB
testcase_21 AC 78 ms
12,160 KB
testcase_22 AC 92 ms
12,288 KB
testcase_23 AC 82 ms
12,288 KB
testcase_24 AC 85 ms
12,160 KB
testcase_25 AC 90 ms
12,416 KB
testcase_26 AC 87 ms
12,544 KB
testcase_27 AC 87 ms
12,416 KB
testcase_28 AC 85 ms
12,288 KB
testcase_29 AC 83 ms
12,288 KB
testcase_30 AC 84 ms
12,416 KB
testcase_31 AC 86 ms
12,288 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:52: warning: assigned but unused variable - r
Syntax OK

ソースコード

diff # 

#!/usr/local/bin/ruby
class BipartiteMatching
  def initialize(n,adj)
    @n,@adj = n,adj # adj is already satisfied with bipartite property.
  end
  private
  def dfs(v)
    rop = false
    @visited[v] = true
    @adj[v].each do |u|
      w = @match[u]
      if w.nil? || (@visited[w].nil? && dfs(w))
        rop,@match[v],@match[u] = true,u,v
        break
      end
    end
    rop
  end
  public
  def matching
    #kuhn algorithm:
    # Start by unsaturated vertex, find an augmenting path, update the matching.
    r = 0
    @match = Array.new(@n)
    (0...@n).each do |i|
      unless @match[i]
        @visited = Array.new(@n)
        if dfs(i)
          r+=1
        end
      end
    end
    [r,@match]
  end
end
class StudentNumber
  def initialize(*arg)
    @n,@a, = arg
    @adj = Array.new(2*@n){Array.new}
    (0...@n).each do |i|
      (0...[@a[i],@n].min).each do |j|
        @adj[i].push(@n+j)
        @adj[@n+j].push(i)
      end
      ([0,@a[i]+1].max...@n).each do |j|
        @adj[i].push(@n+j)
        @adj[@n+j].push(i)
      end
    end
  end
  def ans
    r,marr = BipartiteMatching.new(2*@n,@adj).matching
    if marr.any?(nil)
      [-1]
    else
      marr[0,@n].map{_1-@n}
    end
  end
end
### END: class StudentNumber
iod = STDIN
n = iod.gets.to_i
a = Array.new(n){iod.gets.to_i}
puts StudentNumber.new(n,a).ans
exit 0
0