結果

問題 No.1779 Magical Swap
ユーザー 👑 obakyanobakyan
提出日時 2022-03-13 23:25:50
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 1,758 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 7,076 KB
実行使用メモリ 9,324 KB
最終ジャッジ日時 2024-11-14 06:54:12
合計ジャッジ時間 2,690 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0