結果
問題 | No.1779 Magical Swap |
ユーザー |
|
提出日時 | 2021-12-19 15:00:55 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 1,138 ms |
コンパイル使用メモリ | 108,928 KB |
実行使用メモリ | 44,544 KB |
最終ジャッジ日時 | 2024-09-15 14:33:37 |
合計ジャッジ時間 | 4,328 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Linq; class H { static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse); static void Main() => Console.WriteLine(string.Join("\n", new int[int.Parse(Console.ReadLine())].Select(_ => Solve() ? "Yes" : "No"))); static bool Solve() { var n = int.Parse(Console.ReadLine()); var a = Read(); var b = Read(); var uf = new UF(n); for (int k = 2; k <= n; k++) { for (int x = 2 * k; x <= n; x += k) { uf.Unite(x - k - 1, x - 1); } } foreach (var g in uf.ToGroups()) { var ag = Array.ConvertAll(g, i => a[i]); var bg = Array.ConvertAll(g, i => b[i]); if (!ag.ToHashSet().SetEquals(bg)) return false; } return true; } } class UF { int[] p, sizes; public int GroupsCount; public UF(int n) { p = Enumerable.Range(0, n).ToArray(); sizes = Array.ConvertAll(p, _ => 1); GroupsCount = n; } public int GetRoot(int x) => p[x] == x ? x : p[x] = GetRoot(p[x]); public int GetSize(int x) => sizes[GetRoot(x)]; public bool AreUnited(int x, int y) => GetRoot(x) == GetRoot(y); public bool Unite(int x, int y) { if ((x = GetRoot(x)) == (y = GetRoot(y))) return false; // 要素数が大きいほうのグループにマージします。 if (sizes[x] < sizes[y]) Merge(y, x); else Merge(x, y); return true; } protected virtual void Merge(int x, int y) { p[y] = x; sizes[x] += sizes[y]; --GroupsCount; } public int[][] ToGroups() => Enumerable.Range(0, p.Length).GroupBy(GetRoot).Select(g => g.ToArray()).ToArray(); }