結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
20,352 KB
testcase_01 AC 38 ms
20,224 KB
testcase_02 AC 54 ms
24,704 KB
testcase_03 AC 45 ms
21,376 KB
testcase_04 AC 149 ms
43,392 KB
testcase_05 AC 84 ms
28,160 KB
testcase_06 AC 90 ms
29,312 KB
testcase_07 AC 129 ms
39,040 KB
testcase_08 AC 44 ms
21,120 KB
testcase_09 AC 72 ms
25,728 KB
testcase_10 AC 170 ms
44,544 KB
testcase_11 AC 111 ms
36,096 KB
testcase_12 AC 64 ms
23,936 KB
testcase_13 AC 144 ms
42,368 KB
testcase_14 AC 160 ms
44,288 KB
testcase_15 AC 303 ms
25,344 KB
testcase_16 AC 165 ms
44,032 KB
testcase_17 AC 148 ms
24,320 KB
testcase_18 AC 39 ms
20,352 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