結果
問題 | No.2732 Similar Permutations |
ユーザー |
|
提出日時 | 2024-04-19 23:19:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,953 ms / 2,000 ms |
コード長 | 3,927 bytes |
コンパイル時間 | 3,306 ms |
コンパイル使用メモリ | 256,744 KB |
実行使用メモリ | 16,160 KB |
最終ジャッジ日時 | 2024-10-11 17:52:34 |
合計ジャッジ時間 | 34,772 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 101 |
ソースコード
#line 1 "main.cpp"#ifdef LOCAL#include <local.hpp>#else#include <bits/stdc++.h>#define debug(...) ((void)0)#define postprocess(...) ((void)0)#endif#line 2 "library/misc/xorshift.hpp"#include <bits/stdc++.h>inline uint32_t xorshift32() {static uint32_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count();x ^= x << 13;x ^= x >> 17;x ^= x << 5;return x;}inline uint64_t xorshift64() {static uint64_t x = std::chrono::high_resolution_clock::now().time_since_epoch().count();x ^= x << 13;x ^= x >> 7;x ^= x << 17;return x;}#line 10 "main.cpp"using namespace std;using ll = long long;using ld = long double;struct RNG {void setSeed(uint64_t seed) {seedSet = true;x = seed;}template <class T>T choice(std::vector<T>& v) {assert(!v.empty());return v[range(0, (int)v.size() - 1)];}template <class T>void shuffle(std::vector<T>& v) {const int N = v.size();for (int i = 0; i < N - 1; i++) {const int j = range(i, N - 1);if (i == j) continue;std::swap(v[i], v[j]);}}// generate random integers in [from, to]template <class T, class U>typename std::common_type<T, U>::type range(T from, U to) {static_assert(std::is_integral_v<T>);static_assert(std::is_integral_v<U>);static_assert(std::is_integral_v<typename std::common_type<T, U>::type>);assert(from <= to);uint64_t width = to - from + 1;typename std::common_type<T, U>::type ret = from;ret += xorshift64() % width;return ret;}private:bool seedSet = false;uint64_t x;uint64_t xorshift64() {assert(seedSet);x ^= x << 13;x ^= x >> 7;x ^= x << 17;return x;}} rng;vector<int> random_permutation(const int N, const uint64_t seed) {rng.setSeed(seed);vector<int> ret(N);iota(ret.begin(), ret.end(), 1);rng.shuffle(ret);return ret;}uint64_t memo[1000000];void solve([[maybe_unused]] int test) {auto start = chrono::high_resolution_clock::now();int N;cin >> N;vector<int> A(N);for (auto&& x : A) {cin >> x;}map<int, int> prev;for (int i = 0; i < N; i++) {if (prev.contains(A[i])) {vector<int> P1(N);iota(P1.begin(), P1.end(), 1);auto P2 = P1;swap(P2[i], P2[prev[A[i]]]);for (int i = 0; i < N; i++) {cout << P1[i] << (i == N - 1 ? "\n" : " ");}for (int i = 0; i < N; i++) {cout << P2[i] << (i == N - 1 ? "\n" : " ");}return;}prev[A[i]] = i;}while (true) {auto now = chrono::high_resolution_clock::now();auto ms = chrono::duration_cast<chrono::milliseconds>(now - start).count();if (ms > 1950) break;const uint64_t seed = max(1ul, xorshift64());const auto P = random_permutation(N, seed);int xorsum = 0;for (int i = 0; i < N; i++) {xorsum ^= (P[i] + A[i]);}if (memo[xorsum] > 0) {const auto P2 = random_permutation(N, memo[xorsum]);if (P != P2) {for (int i = 0; i < N; i++) {cout << P[i] << (i == N - 1 ? "\n" : " ");}for (int i = 0; i < N; i++) {cout << P2[i] << (i == N - 1 ? "\n" : " ");}return;}}memo[xorsum] = seed;}cout << -1 << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;// cin >> t;for (int i = 1; i <= t; i++) {solve(i);}postprocess();}