結果

問題 No.1519 Diversity
ユーザー yuruhiyayuruhiya
提出日時 2021-05-28 21:29:50
言語 Crystal
(1.11.2)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 5,083 bytes
コンパイル時間 14,430 ms
コンパイル使用メモリ 294,924 KB
実行使用メモリ 11,336 KB
最終ジャッジ日時 2024-11-07 09:02:16
合計ジャッジ時間 14,392 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 8 ms
5,248 KB
testcase_04 AC 14 ms
6,528 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 18 ms
8,192 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 5 ms
5,248 KB
testcase_09 AC 8 ms
5,248 KB
testcase_10 AC 14 ms
7,424 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 17 ms
6,400 KB
testcase_13 AC 20 ms
11,136 KB
testcase_14 AC 20 ms
11,336 KB
testcase_15 AC 19 ms
7,936 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "graph"
struct Edge(T)
  include Comparable(Edge(T))

  property to : Int32
  property cost : T

  def initialize(@to : Int32, @cost : T)
  end

  def <=>(other : Edge(T))
    {cost, to} <=> {other.cost, other.to}
  end

  def to_s(io) : Nil
    io << '(' << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "->#{to}(#{cost})"
  end
end

struct Edge2(T)
  include Comparable(Edge2(T))

  property from : Int32
  property to : Int32
  property cost : T

  def initialize(@from : Int32, @to : Int32, @cost : T)
  end

  def <=>(other : Edge2(T))
    {cost, from, to} <=> {other.cost, other.from, other.to}
  end

  def reverse
    Edge2(T).new(to, from, cost)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ", " << cost << ')'
  end

  def inspect(io) : Nil
    io << "#{from}->#{to}(#{cost})"
  end
end

struct UnweightedEdge2
  property from : Int32
  property to : Int32

  def initialize(@from, @to)
  end

  def reverse
    UnweightedEdge2.new(to, from)
  end

  def to_s(io) : Nil
    io << '(' << from << ", " << to << ')'
  end

  def inspect(io) : Nil
    io << "#{from}->#{to}"
  end
end

abstract class Graph(T)
  getter graph : Array(Array(Edge(T)))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Edge(T)).new }
  end

  abstract def add_edge(edge : Edge2(T))
  abstract def add_edges(edges : Array(Edge2(T)))

  def add_edge(i : Int32, j : Int32, cost : T)
    add_edge(Edge2.new(i, j, cost))
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |edge|
        yield Edge2(T).new(v, edge.to, edge.cost)
      end
    end
  end

  def edges : Array(Edge2(T))
    result = [] of Edge2(T)
    each_edge do |edge|
      result << edge
    end
    result
  end
end

class DirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    self
  end

  def add_edges(edges : Array(Edge2(T)))
    edges.each { |edge| add_edge(edge) }
    self
  end
end

class UndirectedGraph(T) < Graph(T)
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(Edge2(T)))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : Edge2(T))
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << Edge.new(edge.to, edge.cost)
    @graph[edge.to] << Edge.new(edge.from, edge.cost)
    self
  end

  def add_edges(edges : Array(Edge2(T)))
    edges.each { |edge| add_edge(edge) }
    self
  end
end

abstract class UnweightedGraph
  getter graph : Array(Array(Int32))

  def initialize(size : Int)
    raise ArgumentError.new("Negative graph size: #{size}") unless size >= 0
    @graph = Array.new(size) { Array(Int32).new }
  end

  abstract def add_edge(edge : UnweightedEdge2)
  abstract def add_edges(edges : Array(UnweightedEdge2))

  def add_edge(i : Int32, j : Int32)
    add_edge(UnweightedEdge2.new(i, j))
  end

  delegate size, to: @graph
  delegate :[], to: @graph

  def each_edge : Nil
    (0...size).each do |v|
      graph[v].each do |u|
        yield UnweightedEdge2.new(v, u)
      end
    end
  end

  def edges : Array(UnweightedEdge2)
    result = [] of UnweightedEdge2
    each_edge do |edge|
      result << edge
    end
    result
  end
end

class UnweightedDirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(UnweightedEdge2))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << edge.to
    self
  end

  def add_edges(edges : Array(UnweightedEdge2))
    edges.each { |edge| add_edge(edge) }
    self
  end
end

class UnweightedUndirectedGraph < UnweightedGraph
  def initialize(size : Int)
    super
  end

  def initialize(size : Int, edges : Array(UnweightedEdge2))
    super(size)
    add_edges(edges)
  end

  def add_edge(edge : UnweightedEdge2)
    raise IndexError.new unless 0 <= edge.from < size
    raise IndexError.new unless 0 <= edge.to < size
    @graph[edge.from] << edge.to
    @graph[edge.to] << edge.from
    self
  end

  def add_edges(edges : Array(UnweightedEdge2))
    edges.each { |edge| add_edge(edge) }
    self
  end
end

n = read_line.to_i
g = UnweightedUndirectedGraph.new(n)
(1...n).reverse_each do |i|
  v = 0
  while g[i].size < i
    if v == 0
      g.add_edge(i, v)
      v = i - 1
    else
      g.add_edge(i, v)
      v = v - 1
    end
  end
end
puts g.edges.size // 2
puts g.edges.select { |e| e.from < e.to }.join('\n') { |e|
  "#{e.from + 1} #{e.to + 1}"
}
0