結果

問題 No.1779 Magical Swap
コンテスト
ユーザー XD
提出日時 2021-12-11 16:58:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 1,680 bytes
コンパイル時間 2,025 ms
コンパイル使用メモリ 178,020 KB
実行使用メモリ 16,544 KB
最終ジャッジ日時 2024-11-08 10:15:19
合計ジャッジ時間 4,439 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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