思路
对于p数组,每个数只有两个禁止的位置不能是自己,并且a[pi]也不是。
也就是每个点限制有两个位置不能放,可行的种类有很多,但是模拟起来又
较复杂,所以采用随机数
代码
/*
可能的情况有很多,直接使用随机数就可以了
只要不和两个位置重合就可以了
*/
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 5;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());//随机数
int a[M], p[M], q[M];
void solve() {
int n; cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = 1; i <= n; i++)p[i] = i;
int cnt = 1000;
while(cnt--) {
bool flag = 1;
shuffle(p + 1, p + 1 + n, rng);
for(int i = 1; i <= n; i++)
if(p[i] == i || a[p[i]] == i)flag = 0;
if(flag) {
cout <<"Possible\n";
for(int i = 1; i <= n; i++)cout << p[i] << ' '; cout << '\n';
for(int i = 1; i <= n; i++)p[i] = a[p[i]], q[p[i]] = i;
for(int i = 1; i <= n; i++)cout << q[i] << ' '; cout << '\n';
return ;
}
}
cout <<"Impossible\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TT; cin >> TT;
while(TT--) {
solve();
}
return 0;
}
标签:int,TT,Trick,Amazing,solve,随机数
From: https://www.cnblogs.com/basicecho/p/17181099.html