結果
問題 | No.1779 Magical Swap |
ユーザー |
![]() |
提出日時 | 2021-12-08 22:21:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 4,880 bytes |
コンパイル時間 | 1,656 ms |
コンパイル使用メモリ | 133,384 KB |
最終ジャッジ日時 | 2025-01-26 06:58:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 18 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cmath>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <tuple>#include <utility>#include <unordered_map>#include <unordered_set>#include <vector>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (n); ++i)#define REP3(i, m, n) for (i32 i = (m); i < (n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER(i, n) for (i32 i = (n) - 1; i >= 0; --i)#define ALL(x) begin(x), end(x)using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using u128 = __uint128_t;using i32 = signed int;using i64 = signed long long;using i128 = __int128_t;template <typename T>using Vec = vector<T>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}[[maybe_unused]] constexpr i32 inf = 1000000100;[[maybe_unused]] constexpr i64 inf64 = 3000000000000000100;struct SetIO {SetIO() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(10);}} set_io;// ===== new_library/graph/graph.hpp =====#include <vector>#include <utility>template <typename Edge>class Graph {std::vector<std::vector<Edge>> edges;public:Graph() : edges() {}Graph(std::size_t v) : edges(v) {}template <typename... T>void add_edge(std::size_t from, std::size_t to, T &&... val) {edges[from].emplace_back(Edge(to, std::forward<T>(val) ...));}template <typename... T>void add_undirected_edge(std::size_t u, std::size_t v, const T &... val) {edges[u].emplace_back(Edge(v, val...));edges[v].emplace_back(Edge(u, val...));}std::size_t size() const {return edges.size();}const std::vector<Edge> &operator[](std::size_t v) const {return edges[v];}std::vector<Edge> &operator[](std::size_t v) {return edges[v];}};template <typename T>struct WeightedEdge {std::size_t to;T weight;WeightedEdge(std::size_t t, const T &w) : to(t), weight(w) {}operator std::size_t() const {return to;}};// ===== new_library/graph/graph.hpp =====// ===== new_library/graph/connected_components.hpp =====#include <vector>#include <queue>#include <utility>class ConnectedComponents {std::vector<std::size_t> number;std::size_t comp;public:template <typename G>ConnectedComponents(const G &graph) : number(graph.size(), graph.size()) , comp(0) {std::queue<std::size_t> que;for (std::size_t i = 0; i < graph.size(); ++i) {if (number[i] != graph.size())continue;que.push(i);number[i] = comp;while (!que.empty()) {std::size_t v = que.front();que.pop();for (const auto &e : graph[v]) {if (number[(std::size_t) e] == graph.size()) {number[(std::size_t) e] = number[v];que.push((std::size_t) e);}}}++comp;}}std::size_t operator[](std::size_t v) const {return number[v];}std::vector<std::vector<std::size_t>> group() const {std::vector<std::vector<std::size_t>> ret(comp);for (std::size_t i = 0; i < number.size(); ++i)ret[number[i]].push_back(i);return ret;}std::size_t components() const {return comp;}};// ===== new_library/graph/connected_components.hpp =====bool solve(i32 n, Vec<i32> a, Vec<i32> b) {Graph<i32> g(n + 1);REP(k, 2, n + 1) {for (i32 i = k; i + k <= n; i += k) {g.add_undirected_edge(i, i + k);}}ConnectedComponents cc(g);auto comp = cc.group();for (const auto &vs : comp) {if (vs[0] == 0) continue;Vec<i32> sa, sb;sa.resize(vs.size());sb.resize(vs.size());for (i32 i : vs) {sa.push_back(a[i]);sb.push_back(b[i]);}sort(ALL(sa));sort(ALL(sb));if (sa != sb) {return false;}}return true;}int main() {i32 t;cin >> t;while (t--) {i32 n;cin >> n;Vec<i32> a(n + 1, 0), b(n + 1, 0);REP(i, n) cin >> a[i + 1];REP(i, n) cin >> b[i + 1];cout << (solve(n, move(a), move(b)) ? "Yes\n" : "No\n");}}