結果
問題 | No.2732 Similar Permutations |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:40:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 7,101 bytes |
コンパイル時間 | 3,044 ms |
コンパイル使用メモリ | 225,276 KB |
最終ジャッジ日時 | 2025-02-21 04:53:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 101 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int INF = 1e9 + 10;const ll INFL = 4e18;namespace random_generator {mt19937_64 generate;void init() {random_device seed_gen;generate = mt19937_64(seed_gen());}template <typename T>T random_int(T x) {assert(x > 0);return generate() % x;}template <typename T>T random_int(T x, T y) {assert(x < y);return x + generate() % (y - x);}template <typename T>T get_elememt(vector<T>& a) {const int n = a.size();int idx = random_int(0, n);swap(a[n - 1], a[idx]);int ret = a.back();a.pop_back();return ret;}template <typename T>vector<T> random_array_int(int n, T lo, T hi, bool no_dup = false) {vector<T> ret(n);if (!no_dup) {for (int i = 0; i < n; i++) {ret[i] = random_int(lo, hi);}} else {set<T> st;for (int i = 0; i < n; i++) {int r = random_int(lo, hi);while (st.count(r)) {r = random_int(lo, hi);}ret[i] = r;st.insert(r);}}return ret;}string random_alphabet(int n, bool lower = true) {string ret;for (int i = 0; i < n; i++) {int idx = random_int(26);ret.push_back(char((lower ? 'a' : 'A') + idx));}return ret;}string random_string(int n, string s) {string ret;int m = s.size();for (int i = 0; i < n; i++) {int idx = random_int(m);ret.push_back(s[idx]);}return ret;}template <typename T>vector<vector<T>> random_array_2D(int h, int w, T lo, T hi) {vector<vector<T>> ret(h, vector<T>(w));for (int i = 0; i < h; i++) {ret[i] = random_array_int(w, lo, hi);}return ret;}vector<string> random_alphabet_2D(int h, int w, bool lower = true) {vector<string> ret(h);for (int i = 0; i < h; i++) {ret[i] = random_alphabet(w, lower);}return ret;}vector<pair<int, int>> random_tree(int n) {vector<int> a = random_array_int<int>(n - 2, 1, n + 1);vector<int> d(n + 1);for (int i = 0; i < n - 2; i++) {d[a[i]]++;}for (int i = 1; i <= n; i++) {d[i]++;}vector<pair<int, int>> ret;set<int> pq;for (int i = 1; i <= n; i++) {if (d[i] == 1) {pq.insert(i);}}for (int i = 0; i < n - 2; i++) {int v = (*pq.begin());pq.erase(v);ret.push_back(make_pair(v, a[i]));d[v]--;d[a[i]]--;if (d[a[i]] == 1) {pq.insert(a[i]);} else if (d[a[i]] == 0) {pq.erase(a[i]);}}for (int i = 1; i <= n; i++) {if (d[i] == 1) {for (int j = i + 1; j <= n; j++) {if (d[j] == 1) {ret.push_back(make_pair(i, j));break;}}break;}}return ret;}vector<pair<int, int>> random_bintree(int n) {vector<pair<int, int>> ret;vector<ll> roots = {random_int(1, n + 1)};vector<ll> leaves;for (int i = 1; i <= n; i++) {if (i != roots.back()) {leaves.push_back(i);}}while (!leaves.empty()) {int root = get_elememt(roots);int leaf = get_elememt(leaves);ret.push_back(make_pair(root, leaf));roots.push_back(leaf);if (!leaves.empty()) {int leaf = get_elememt(leaves);ret.push_back(make_pair(root, leaf));roots.push_back(leaf);}}return ret;}vector<pair<int, int>> random_undigraph(int n, int m, bool connected = true) {vector<pair<int, int>> edges;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {edges.push_back(make_pair(i + 1, j + 1));}}int ed = edges.size();if (!connected) {vector<pair<int, int>> ret;vector<int> idxs = random_array_int<int>(m, 0, ed, true);for (int idx : idxs) {ret.push_back(edges[idx]);}return ret;} else {vector<pair<int, int>> ret;while (true) {ret.clear();vector<int> idxs = random_array_int<int>(m, 0, ed, true);vector<int> parent(n);vector<vector<int>> sets(n);for (int i = 0; i < n; i++) {parent[i] = i;sets[i].push_back(i);}for (int idx : idxs) {ret.push_back(edges[idx]);auto [a, b] = edges[idx];a--;b--;if (parent[a] != parent[b]) {if (sets[parent[a]].size() < sets[parent[b]].size()) {swap(a, b);}for (int x : sets[parent[b]]) {parent[x] = parent[a];sets[parent[a]].push_back(x);}sets[parent[b]].clear();}}bool ok = true;for (int i = 0; i < n; i++) {if (parent[i] != parent[0]) {ok = false;break;}}if (ok) {return ret;}}}}}; // namespace random_generatorstruct setup_random {setup_random() {random_generator::init();}} setup_random_instance;int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}vector<int> P(N);iota(P.begin(), P.end(), 1);map<int, vector<int>> mp;do {int xorsum = 0;for (int i = 0; i < N; i++) {xorsum ^= (A[i] + P[i]);}if (mp.find(xorsum) != mp.end()) {for (int i = 0; i < N; i++) {cout << mp[xorsum][i] << " ";}cout << endl;for (int i = 0; i < N; i++) {cout << P[i] << " ";}cout << endl;return 0;} else {mp[xorsum] = P;}} while (next_permutation(P.begin(), P.end()));cout << -1 << endl;}