結果
問題 | No.1779 Magical Swap |
ユーザー |
![]() |
提出日時 | 2021-12-08 00:06:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,195 bytes |
コンパイル時間 | 2,023 ms |
コンパイル使用メモリ | 181,944 KB |
実行使用メモリ | 19,908 KB |
最終ジャッジ日時 | 2024-07-16 07:37:09 |
合計ジャッジ時間 | 4,100 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int T; cin >> T; for (int i = 0; i < T; i++){ int N; cin >> N; vector<int> A(N); for (int j = 0; j < N; j++){ cin >> A[j]; } vector<int> B(N); for (int j = 0; j < N; j++){ cin >> B[j]; } vector<vector<int>> E(N); for (int j = 2; j <= N; j++){ for (int k = j * 2; k <= N; k += j){ E[j - 1].push_back(k - 1); E[k - 1].push_back(j - 1); } } vector<bool> used(N, false); bool ok = true; for (int j = 0; j < N; j++){ if (!used[j]){ used[j] = true; vector<int> a, b; queue<int> Q; Q.push(j); while (!Q.empty()){ int v = Q.front(); Q.pop(); a.push_back(A[v]); b.push_back(B[v]); for (int w : E[v]){ if (!used[w]){ used[w] = true; Q.push(w); } } } sort(a.begin(), a.end()); sort(b.begin(), b.end()); if (a != b){ ok = false; } } } if (ok){ cout << "Yes" << endl; } else { cout << "No" << endl; } } }