結果

問題 No.1779 Magical Swap
ユーザー XDXD
提出日時 2021-12-11 16:58:49
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 1,680 bytes
コンパイル時間 2,168 ms
コンパイル使用メモリ 176,860 KB
実行使用メモリ 17,028 KB
最終ジャッジ日時 2023-08-08 04:28:27
合計ジャッジ時間 5,184 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,740 KB
testcase_01 AC 4 ms
7,740 KB
testcase_02 AC 7 ms
7,660 KB
testcase_03 AC 6 ms
7,708 KB
testcase_04 AC 28 ms
8,160 KB
testcase_05 AC 15 ms
8,020 KB
testcase_06 AC 16 ms
7,736 KB
testcase_07 AC 25 ms
8,028 KB
testcase_08 AC 5 ms
7,724 KB
testcase_09 AC 32 ms
9,636 KB
testcase_10 AC 161 ms
16,148 KB
testcase_11 AC 70 ms
11,876 KB
testcase_12 AC 22 ms
9,364 KB
testcase_13 AC 118 ms
14,120 KB
testcase_14 AC 188 ms
17,028 KB
testcase_15 AC 46 ms
7,648 KB
testcase_16 AC 32 ms
8,192 KB
testcase_17 AC 63 ms
7,668 KB
testcase_18 AC 4 ms
7,644 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define forn(i,s,t) for(register int i=(s); i<=(t); ++i)
#define form(i,s,t) for(register int i=(s); i>=(t); --i)
#define rep(i,s,t) for(register int i=(s); i<(t); ++i)
using namespace std;
const int N = 1e5 + 4;
bool vis[N]; int p[N], tot;
inline void table(int n = 1e5) {
	forn (i, 2, n) {
		if (!vis[i]) p[++tot] = i;
		for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0) break ;
		}
	}
}
int n, a[N], b[N], rft[N << 1], fa[N]; map<int, int> Sa, Sb; vector<int> P[N];
int fnd(int u) {return fa[u] == u ? u : fa[u] = fnd(fa[u]); }
inline void mrg(int u, int v) {
	u = fnd(u), v = fnd(v);
	if (u == v) return ;
	fa[v] = u;
}
inline void init() {forn (i, 1, n) P[i].clear(); }
inline void solve() {
	scanf("%d", &n); 
	forn (i, 1, n) scanf("%d", a + i);
	forn (i, 1, n) scanf("%d", b + i);
//	if (a[1] != b[1]) return puts("No"), void();
	forn (i, 1, n) fa[i] = i;
	for (int i = 1; i <= tot && p[i] <= n; ++i) for (int j = p[i] + p[i]; j <= n; j += p[i]) mrg(p[i], j);
	for (int i = 1; i <= tot && p[i] <= n; ++i) {
		int lim = upper_bound(p + 1, p + tot + 1, n / p[i]) - p;
		rep (j, 1, lim) mrg(p[i], p[j]);
	}
	forn (i, 1, n) P[fnd(i)].push_back(i); //printf("%d%c", fnd(i), " \n"[i == n]);
	bool fl = 1;
	forn (i, 1, n) if (i == fnd(i)) {
		Sa.clear(), Sb.clear();
		for (const int& Ps : P[i]) Sa[a[Ps]] ++ , Sb[b[Ps]] ++ ;
		for (const int& Ps : P[i]) {
			if (Sa[a[Ps]] != Sb[a[Ps]]) fl = 0;
//			printf("%d :: %d %d\n", a[Ps], Sa[a[Ps]], Sb[b[Ps]]);
		}
		if (!fl) return puts("No"), void();
	}
	puts("Yes");
}
int Trd;
int main() {
	scanf("%d", &Trd); table();
	while (Trd--) init(), solve();
	return 0;
}
0