結果

問題 No.2732 Similar Permutations
ユーザー nu50218
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0