結果

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