結果

問題 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.

ソースコード

diff #
プレゼンテーションモードにする

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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0