結果

問題 No.1779 Magical Swap
ユーザー 👑 obakyanobakyan
提出日時 2022-03-13 23:25:50
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 165 ms / 2,000 ms
コード長 1,758 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 5,504 KB
実行使用メモリ 9,324 KB
最終ジャッジ日時 2024-04-26 17:23:40
合計ジャッジ時間 2,684 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 13 ms
5,376 KB
testcase_03 AC 5 ms
5,376 KB
testcase_04 AC 44 ms
5,376 KB
testcase_05 AC 19 ms
5,376 KB
testcase_06 AC 21 ms
5,376 KB
testcase_07 AC 38 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 36 ms
5,376 KB
testcase_10 AC 154 ms
9,068 KB
testcase_11 AC 77 ms
5,992 KB
testcase_12 AC 25 ms
5,376 KB
testcase_13 AC 119 ms
8,684 KB
testcase_14 AC 165 ms
9,324 KB
testcase_15 AC 98 ms
5,376 KB
testcase_16 AC 48 ms
5,376 KB
testcase_17 AC 106 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mce, mfl, msq, mmi, mma, mab = math.ceil, math.floor, math.sqrt, math.min, math.max, math.abs

local function getprimes(x)
  local primes = {}
  local allnums = {}
  for i = 1, x do allnums[i] = true end
  for i = 2, x do
    if allnums[i] then
      table.insert(primes, i)
      local lim = mfl(x / i)
      for j = 2, lim do
        allnums[j * i] = false
      end
    end
  end
  return primes
end

local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local function solve()
  local n = io.read("*n")
  local a, b = {}, {}
  for i = 1, n do
    a[i] = io.read("*n")
  end
  for i = 1, n do
    b[i] = io.read("*n")
  end
  if a[1] ~= b[1] then
    return false
  end
  local parent = uf_initialize(n)
  local primes = getprimes(n)
  for i = 1, #primes do
    local p = primes[i]
    local lim = mfl(n / p)
    local r = uf_findroot(p, parent)
    for j = 2, lim do
      local r2 = uf_findroot(p * j, parent)
      parent[r2], parent[p * j] = r, r
    end
  end
  local ta, tb = {}, {}
  for i = 1, n do
    local r = uf_findroot(i, parent)
    if not ta[r] then
      ta[r] = {}
      tb[r] = {}
    end
    table.insert(ta[r], a[i])
    table.insert(tb[r], b[i])
  end
  for k, tta in pairs(ta) do
    local ttb = tb[k]
    table.sort(tta)
    table.sort(ttb)
    for i = 1, #tta do
      if tta[i] ~= ttb[i] then return false end
    end
  end
  return true
end

local q = io.read("*n")
for iq = 1, q do
  print(solve() and "Yes" or "No")
end
0