結果
問題 | No.1779 Magical Swap |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
local mce, mfl, msq, mmi, mma, mab = math.ceil, math.floor, math.sqrt, math.min, math.max, math.abslocal function getprimes(x)local primes = {}local allnums = {}for i = 1, x do allnums[i] = true endfor i = 2, x doif allnums[i] thentable.insert(primes, i)local lim = mfl(x / i)for j = 2, lim doallnums[j * i] = falseendendendreturn primesendlocal function uf_initialize(n)local parent = {}for i = 1, n do parent[i] = i endreturn parentendlocal function uf_findroot(idx, parent)local idx_update = idxwhile parent[idx] ~= idx doidx = parent[idx]endwhile parent[idx_update] ~= idx doparent[idx_update], idx_update = idx, parent[idx_update]endreturn idxendlocal function solve()local n = io.read("*n")local a, b = {}, {}for i = 1, n doa[i] = io.read("*n")endfor i = 1, n dob[i] = io.read("*n")endif a[1] ~= b[1] thenreturn falseendlocal parent = uf_initialize(n)local primes = getprimes(n)for i = 1, #primes dolocal p = primes[i]local lim = mfl(n / p)local r = uf_findroot(p, parent)for j = 2, lim dolocal r2 = uf_findroot(p * j, parent)parent[r2], parent[p * j] = r, rendendlocal ta, tb = {}, {}for i = 1, n dolocal r = uf_findroot(i, parent)if not ta[r] thenta[r] = {}tb[r] = {}endtable.insert(ta[r], a[i])table.insert(tb[r], b[i])endfor k, tta in pairs(ta) dolocal ttb = tb[k]table.sort(tta)table.sort(ttb)for i = 1, #tta doif tta[i] ~= ttb[i] then return false endendendreturn trueendlocal q = io.read("*n")for iq = 1, q doprint(solve() and "Yes" or "No")end