結果
問題 | No.1779 Magical Swap |
ユーザー |
![]() |
提出日時 | 2021-12-09 13:12:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 2,112 bytes |
コンパイル時間 | 2,321 ms |
コンパイル使用メモリ | 209,836 KB |
最終ジャッジ日時 | 2025-01-26 07:15:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; class DisjointSet { public: explicit DisjointSet(const std::size_t n) : nodes(n, Node(n, 1)) {} std::size_t size() const { return nodes.size(); } std::size_t size(const std::size_t x) { return nodes[find(x)].size; } std::size_t find(const std::size_t x) { if (nodes[x].parent == size()) return x; return nodes[x].parent = find(nodes[x].parent); } bool is_same(const std::size_t x, const std::size_t y) { return find(x) == find(y); } bool unite(const std::size_t x, const std::size_t y) { std::size_t rx = find(x), ry = find(y); if (rx == ry) return false; if (nodes[rx].size < nodes[ry].size) std::swap(rx, ry); nodes[rx].size += nodes[ry].size; nodes[ry].parent = rx; return true; } private: class Node { private: friend DisjointSet; Node(const std::size_t parent, const std::size_t size) : parent(parent), size(size) {} std::size_t parent; std::size_t size; }; std::vector<Node> nodes; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; auto solve = [&]() { int N; cin >> N; vector<int> A(N), B(N); for (auto &&e : A) { cin >> e; } for (auto &&e : B) { cin >> e; } DisjointSet ds(N); for (int k = 2; k < N; k++) { for (int i = 1; k * (i + 1) - 1 < N; i++) { ds.unite(k * i - 1, k * (i + 1) - 1); } } map<int, multiset<int>> mp; for (int i = 0; i < N; i++) { mp[ds.find(i)].insert(B[i]); } bool ok = true; for (int i = 0; i < N; i++) { // for (const auto &[key, value] : mp) { // cerr << "[+]" << ' ' << key << endl; // for (const auto &e : value) { // cerr << e << '\n'; // } // } // cerr << "--------" << endl; if (mp[ds.find(i)].find(A[i]) == mp[ds.find(i)].end()) { ok = false; break; } mp[ds.find(i)].erase(mp[ds.find(i)].find(A[i])); } cout << (ok ? "Yes" : "No") << '\n'; }; for (int i = 0; i < T; i++) { solve(); } return 0; }