結果

問題 No.1779 Magical Swap
ユーザー さかぽんさかぽん
提出日時 2021-12-19 15:00:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 337 ms / 2,000 ms
コード長 1,535 bytes
コンパイル時間 4,945 ms
コンパイル使用メモリ 108,612 KB
実行使用メモリ 48,636 KB
最終ジャッジ日時 2023-10-13 18:46:42
合計ジャッジ時間 9,048 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
22,984 KB
testcase_01 AC 76 ms
22,636 KB
testcase_02 AC 89 ms
29,052 KB
testcase_03 AC 84 ms
22,852 KB
testcase_04 AC 185 ms
45,640 KB
testcase_05 AC 122 ms
29,616 KB
testcase_06 AC 126 ms
32,376 KB
testcase_07 AC 166 ms
41,208 KB
testcase_08 AC 83 ms
23,132 KB
testcase_09 AC 111 ms
28,228 KB
testcase_10 AC 208 ms
46,536 KB
testcase_11 AC 151 ms
40,368 KB
testcase_12 AC 102 ms
24,656 KB
testcase_13 AC 182 ms
44,372 KB
testcase_14 AC 204 ms
46,480 KB
testcase_15 AC 337 ms
28,148 KB
testcase_16 AC 199 ms
48,636 KB
testcase_17 AC 177 ms
29,020 KB
testcase_18 AC 74 ms
24,724 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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