結果
| 問題 | No.2732 Similar Permutations |
| ユーザー |
 shobonvip
|
| 提出日時 | 2024-04-19 23:19:12 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,520 bytes |
| コンパイル時間 | 4,809 ms |
| コンパイル使用メモリ | 278,108 KB |
| 実行使用メモリ | 20,864 KB |
| 最終ジャッジ日時 | 2024-10-11 17:51:31 |
| 合計ジャッジ時間 | 10,235 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 13 ms
20,864 KB |
| testcase_01 | AC | 13 ms
15,488 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
| testcase_100 | -- | - |
| testcase_101 | -- | - |
| testcase_102 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/
/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/
typedef long long ll;
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
template <typename T> bool chmin(T &a, const T &b) {
if (a <= b) return false;
a = b;
return true;
}
template <typename T> bool chmax(T &a, const T &b) {
if (a >= b) return false;
a = b;
return true;
}
template <typename T> T max(vector<T> &a){
assert(!a.empty());
T ret = a[0];
for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
return ret;
}
template <typename T> T min(vector<T> &a){
assert(!a.empty());
T ret = a[0];
for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
return ret;
}
template <typename T> T sum(vector<T> &a){
T ret = 0;
for (int i=0; i<(int)a.size(); i++) ret += a[i];
return ret;
}
int main(){
random_device seed_gen;
mt19937 engine(seed_gen());
int n; cin >> n;
vector<int> a(n);
rep(i,0,n) cin >> a[i];
if (n <= 10){
vector<int> p(n);
iota(p.begin(),p.end(),1);
vector mem(1<<19,vector<int>(0));
do{
int r=0;
rep(i,0,n)r^=a[i]+p[i];
if(mem[r].size()>0){
rep(i,0,n){
cout << mem[r][i] << ' ';
}
cout << '\n';
rep(i,0,n){
cout << p[i] << ' ';
}
cout << '\n';
return 0;
}
mem[r] = p;
}while(next_permutation(p.begin(),p.end()));
cout << -1 << '\n';
}else{
vector<int> mem(1<<19,-1);
vector<int> p(n);
iota(p.begin(), p.end(), 1);
vector<mint> hash1(n);
vector<mint> hash2(n);
uniform_int_distribution<int> dist(0,998244353);
rep(i,0,n){
hash1[i] = dist(engine);
hash2[i] = dist(engine);
}
mint now1=0,now2=0;
int val=0;
rep(i,0,n){
now1 += hash1[i]*p[i];
now2 += hash2[i]*p[i];
val ^= p[i] + a[i];
}
mem[val]=0;
vector<pair<int,int>> sousa;
uniform_int_distribution<int> dist2(0,n-1);
set<pair<int,int>> st;
int cnt = 0;
while(true){
int u=dist2(engine);
int v=dist2(engine);
if(u==v)continue;
now1 -= hash1[u]*p[u];
now2 -= hash2[u]*p[u];
now1 -= hash1[v]*p[v];
now2 -= hash2[v]*p[v];
now1 += hash1[u]*p[v];
now2 += hash2[u]*p[v];
now1 += hash1[v]*p[u];
now2 += hash2[v]*p[u];
val ^= p[u]+a[u];
val ^= p[v]+a[v];
val ^= p[u]+a[v];
val ^= p[v]+a[u];
sousa.push_back(pair(u,v));
swap(p[u],p[v]);
if (st.find(pair(now1.val(),now2.val()))==st.end()){
swap(p[u],p[v]);
sousa.pop_back();
now1 += hash1[u]*p[u];
now2 += hash2[u]*p[u];
now1 += hash1[v]*p[v];
now2 += hash2[v]*p[v];
now1 -= hash1[u]*p[v];
now2 -= hash2[u]*p[v];
now1 -= hash1[v]*p[u];
now2 -= hash2[v]*p[u];
val ^= p[u]+a[u];
val ^= p[v]+a[v];
val ^= p[u]+a[v];
val ^= p[v]+a[u];
continue;
}
cnt++;
st.insert(pair(now1.val(),now2.val()));
if (mem[val]==-1){
mem[val]=cnt;
}else{
{
vector<int> q(n);
iota(q.begin(),q.end(),1);
rep(i,0,mem[val]){
auto[x,y] = sousa[i];
swap(q[x],q[y]);
}
rep(i,0,n){
cout << q[i] << ' ';
}
cout << '\n';
}
{
vector<int> q(n);
iota(q.begin(),q.end(),1);
rep(i,0,cnt){
auto[x,y] = sousa[i];
swap(q[x],q[y]);
}
rep(i,0,n){
cout << q[i] << ' ';
}
cout << '\n';
}
return 0;
}
}
}
}