結果

問題 No.168 ものさし
ユーザー 👑 obakyanobakyan
提出日時 2020-04-23 21:57:56
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 964 ms / 2,000 ms
コード長 1,062 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 6,972 KB
実行使用メモリ 23,784 KB
最終ジャッジ日時 2023-08-04 03:33:23
合計ジャッジ時間 7,339 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
7,220 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,384 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 12 ms
4,376 KB
testcase_11 AC 136 ms
6,892 KB
testcase_12 AC 637 ms
17,648 KB
testcase_13 AC 964 ms
23,784 KB
testcase_14 AC 770 ms
23,668 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 3 ms
4,376 KB
testcase_17 AC 6 ms
4,380 KB
testcase_18 AC 14 ms
4,380 KB
testcase_19 AC 886 ms
22,816 KB
testcase_20 AC 433 ms
23,604 KB
testcase_21 AC 919 ms
23,636 KB
testcase_22 AC 560 ms
23,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

local bls, brs = bit.lshift, bit.rshift
local n = io.read("*n")
local x, y = {}, {}
for i = 1, n do
  x[i], y[i] = io.read("*n", "*n")
end
local edge = {}
for i = 1, n - 1 do
  edge[i] = {}
  for j = i + 1, n do
    edge[i][j - i] = 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j])
  end
end

local asked = {}
local function solve(z)
  z = 1LL * z * z
  for i = 1, n do
    asked[i] = false
  end
  asked[1] = true
  local tasks = {1}
  while 0 < #tasks do
    local src = tasks[#tasks]
    table.remove(tasks)
    for dst = 1, n do
      local ok = false
      if src < dst then
        ok = edge[src][dst - src] <= z
      elseif dst < src then
        ok = edge[dst][src - dst] <= z
      end
      if ok then
        if not asked[dst] then
          asked[dst] = true
          table.insert(tasks, dst)
        end
      end
    end
  end
  return asked[n]
end
local min, max = 0, 150000000
while 1 < max - min do
  local mid = brs(min + max, 1)
  if solve(mid * 10) then
    max = mid
  else
    min = mid
  end
end
print(max * 10)
0