結果

問題 No.282 おもりと天秤(2)
ユーザー simansiman
提出日時 2022-01-13 04:53:33
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,296 ms / 5,000 ms
コード長 1,537 bytes
コンパイル時間 38 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 31,072 KB
平均クエリ数 214.29
最終ジャッジ日時 2024-07-17 03:07:13
合計ジャッジ時間 13,966 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 118 ms
29,016 KB
testcase_01 AC 127 ms
29,400 KB
testcase_02 AC 118 ms
28,632 KB
testcase_03 AC 116 ms
28,632 KB
testcase_04 AC 115 ms
28,376 KB
testcase_05 AC 121 ms
28,888 KB
testcase_06 AC 126 ms
28,888 KB
testcase_07 AC 114 ms
29,272 KB
testcase_08 AC 127 ms
29,272 KB
testcase_09 AC 112 ms
28,632 KB
testcase_10 AC 413 ms
30,040 KB
testcase_11 AC 1,159 ms
30,552 KB
testcase_12 AC 448 ms
30,296 KB
testcase_13 AC 620 ms
29,784 KB
testcase_14 AC 1,010 ms
30,040 KB
testcase_15 AC 1,222 ms
30,552 KB
testcase_16 AC 192 ms
30,040 KB
testcase_17 AC 578 ms
29,400 KB
testcase_18 AC 882 ms
30,552 KB
testcase_19 AC 900 ms
30,296 KB
testcase_20 AC 1,296 ms
30,944 KB
testcase_21 AC 1,282 ms
30,688 KB
testcase_22 AC 690 ms
31,072 KB
testcase_23 AC 114 ms
28,896 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

N = gets.to_i
omori = [*1..N]
R = Array.new(N + 1) { Array.new(N + 1, 0) }

def merge_sort(l, r, arr, stack, checked)
  return [arr[l]] if r - l == 0
  return [] if r - l < 0
 
  mid = (l + r) / 2
  que_a = merge_sort(l, mid, arr, stack, checked)
  que_b = merge_sort(mid + 1, r, arr, stack, checked)
  ret = []
 
  while !que_a.empty? || !que_b.empty?
    if que_a.empty?
      ret << que_b.shift
    elsif que_b.empty?
      ret << que_a.shift
    elsif R[que_a.first][que_b.first] == -1
      ret << que_a.shift
    elsif R[que_b.first][que_a.first] == -1
      ret << que_b.shift
    else
      if !checked[que_a.first] && !checked[que_b.first]
        checked[que_a.first] = true
        checked[que_b.first] = true
        stack << [que_a.first, que_b.first]
      end

      ret << que_a.shift
    end
  end
 
  ret
end

def send_query(stack)
  query = Array.new(2 * N, 0)

  stack.each_with_index do |(i, j), idx|
    break if idx >= N

    query[2 * idx] = i
    query[2 * idx + 1] = j
  end

  STDOUT.puts("? #{query.join(' ')}")
  STDOUT.flush

  res = gets.chomp.split

  res.each_with_index do |r, idx|
    i, j = stack[idx]
    break if i.nil?

    if r == '<'
      R[i][j] = -1
      R[j][i] = 1
    else
      R[i][j] = 1
      R[j][i] = -1
    end
  end
end

loop do
  stack = []
  checked = Array.new(N + 1, false)
  merge_sort(0, N - 1, omori, stack, checked)

  break if stack.empty?
  send_query(stack)
end

checked = Array.new(N + 1, false)
ans = merge_sort(0, N - 1, omori, [], checked)
puts "! #{ans.join(' ')}"
0