結果
問題 | 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();}