fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11. 	vector<int> a(n), b(n);
  12. 	for(int i = 0; i < n; i++){
  13. 		cin >> a[i];
  14. 		b[a[i] - 1] = i + 1;
  15. 	}
  16. 	set<int> s;
  17. 	s.insert(0);
  18. 	for(int i = 0; i < n; i++){
  19. 		if(b[i] < i + 1){
  20. 			int dist = (i + 1) - b[i];
  21. 			s.insert(dist);
  22. 		}else{
  23. 			int dist = n - (b[i] - (i + 1));
  24. 			s.insert(dist);
  25. 		}
  26. 	}
  27.  
  28. 	for(int i = 1; i < n; i++){
  29. 		if(s.find(i) == s.end()){
  30. 			cout << "Possible\n";
  31. 			for(int j = i; j < n; j++)cout << b[j] << " ";
  32. 			for(int j = 0; j < i; j++)cout << b[j] << " ";
  33. 			cout << "\n";
  34. 			for(int j = n - i + 1; j <= n; j++)cout << j << " ";
  35. 			for(int j = 1; j < n - i + 1; j++)cout << j << " ";
  36. 			cout << "\n";
  37. 			return;
  38. 		}
  39. 	}
  40. 	cout << "Impossible\n";
  41. }
  42.  
  43. int main(){
  44. 	ios_base::sync_with_stdio(false);
  45. 	cin.tie(nullptr);
  46.  
  47. 	int t = 1;
  48. 	cin >> t;
  49.  
  50. 	for(int i = 1; i <= t; i++){
  51. 		solve();
  52. 	}
  53. 	return 0;
  54. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4
2
2 1
3
1 2 3
4
2 1 4 3
5
5 1 4 2 3
stdout
copy 
Impossible
Possible
2 3 1 
3 1 2 
Possible
4 3 2 1 
3 4 1 2 
Possible
5 3 1 2 4 
4 5 1 2 3
https://ideone.com/4SqbHD
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!