#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,t,tes,f[200009],boo,pi,k[200009],qi,qqi,bo[200009],sup;
pair <int, int> p[3000009],q[200009],qq[200009];
void sw(int q, int w){
swap(f[q],f[w]);
swap(f[a-q+1],f[a-w+1]);
}
void dfs(int q){
//zx++;
bo[q]=t;
if(f[q]<=a/2){
if(bo[f[q]]==t) return;
dfs(f[q]);
}else{
zx++;
if(bo[a+1-f[q]]==t) return;
dfs(a+1-f[q]);
}
}
int main(){
//ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//cin>>tes;
scanf("%d\n",&tes);
for(t=1; t<=tes; t++){
//cin>>a;
if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
for(i=1; i<=a; i++){
//cin>>f[i];
if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
}
boo=0;
for(i=1; i<=a/2; i++){
if(f[i]>a/2){
boo=1;
break;
}
}
if(boo==0){
/*boo=0;
for(i=1; i<=a/2; i++){
if(f[a-i+1]-f[i]!=a/2){
boo=1;
break;
}
}
if(boo==1){
cout<<-1<<endl;
continue;
}*/
pi=0;
for(i=1; i<=a/2; i++){
k[f[i]]=i;
}
for(i=1; i<=a/2; i++){
if(k[i]==i) continue;
pi++;
p[pi].first=k[i];
p[pi].second=i;
c=k[i];d=i;
swap(k[i],k[f[i]]);
swap(f[c],f[d]);
}
for(i=1; i<=pi; i++){
swap(f[a-p[i].first+1],f[a-p[i].second+1]);
}
boo=0;
for(i=2; i<=a; i++){
if(f[i]<f[i-1]){
boo=1;
break;
}
}
if(boo==1){
// cout<<-1<<endl;
printf("-1\n");
continue;
}
//cout<<pi<<" "<<pi<<endl;
printf("%d %d\n",pi,pi);
for(i=1; i<=pi; i++){
//cout<<p[i].first<<" "<<p[i].second<<endl;
printf("%d %d\n",p[i].first,p[i].second);
}
continue;
}
boo=0;
for(i=1; i<=a/2; i++){
j=a-i+1;
if(f[i]+f[j]!=a+1){
boo=1;
break;
}
}
if(boo==0){
//printf("%d 0\n",a);
}else{
printf("-1\n");
continue;
}
qi=0;qqi=0;
for(i=1; i<=a/2; i++){
if(f[i]>f[a-i+1]){
qi++;
q[qi].first=i;
q[qi].second=a-i+1;
}else{
/*qqi++;
qq[qqi].first=a-i+1;
qq[qqi].second=i;*/
}
}
if(qi%2==1){
printf("-1\n");
continue;
}else{
//printf("%d 0\n",a);
}
c=0;d=0;e=0;
for(i=1; i<=a/2; i++){
if(bo[i]==t) continue;
e++;
zx=0;
dfs(i);
c+=zx/2;
d+=zx%2;
}
sup=a/2-(e+c-d/2)+qi/2;
//printf("%d 0\n",a/2-(e+c-d/2)+qi/2);
pi=0;
for(i=1; i+1<=qi; i+=2){
pi++;
p[pi].first=q[i].second;p[pi].second=q[i+1].first;
sw(q[i].second,q[i+1].first);
}
//sample
for(i=1; i<=a/2; i++){
k[f[i]]=i;
}
for(i=1; i<=a/2; i++){
if(k[i]==i) continue;
pi++;
p[pi].first=k[i];
p[pi].second=i;
c=k[i];d=i;
swap(k[i],k[f[i]]);
swap(f[c],f[d]);
}
printf("%d %d\n",sup,pi);
for(i=1; i<=pi; i++){
//cout<<p[i].first<<" "<<p[i].second<<endl;
printf("%d %d\n",p[i].first,p[i].second);
}
}
return 0;
}
Compilation message
cat.cpp: In function 'int main()':
cat.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
24 | scanf("%d\n",&tes);
| ~~~~~^~~~~~~~~~~~~
cat.cpp:27:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
| ~~~~~^~~~~~~~~~~
cat.cpp:27:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
| ~~~~~^~~~~~~~~
cat.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
30 | if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
| ~~~~~^~~~~~~~~~~~
cat.cpp:30:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
30 | if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
364 KB |
Correct number of moves and valid reconstruction |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
620 KB |
Output is correct |
| 2 |
Correct |
28 ms |
620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
364 KB |
Correct number of moves and valid reconstruction |
| 2 |
Correct |
29 ms |
620 KB |
Output is correct |
| 3 |
Correct |
28 ms |
620 KB |
Output is correct |
| 4 |
Correct |
33 ms |
748 KB |
Correct number of moves and valid reconstruction |
| 5 |
Correct |
13 ms |
492 KB |
Correct number of moves and valid reconstruction |
| 6 |
Correct |
10 ms |
492 KB |
Correct number of moves and valid reconstruction |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
620 KB |
Output is correct |
| 2 |
Correct |
28 ms |
620 KB |
Output is correct |
| 3 |
Correct |
589 ms |
13036 KB |
Output is correct |
| 4 |
Correct |
569 ms |
11884 KB |
Output is correct |
| 5 |
Correct |
603 ms |
14572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
364 KB |
Correct number of moves and valid reconstruction |
| 2 |
Correct |
29 ms |
620 KB |
Output is correct |
| 3 |
Correct |
28 ms |
620 KB |
Output is correct |
| 4 |
Correct |
33 ms |
748 KB |
Correct number of moves and valid reconstruction |
| 5 |
Correct |
13 ms |
492 KB |
Correct number of moves and valid reconstruction |
| 6 |
Correct |
10 ms |
492 KB |
Correct number of moves and valid reconstruction |
| 7 |
Correct |
589 ms |
13036 KB |
Output is correct |
| 8 |
Correct |
569 ms |
11884 KB |
Output is correct |
| 9 |
Correct |
603 ms |
14572 KB |
Output is correct |
| 10 |
Correct |
653 ms |
14316 KB |
Correct number of moves and valid reconstruction |
| 11 |
Correct |
598 ms |
12012 KB |
Correct number of moves and valid reconstruction |
| 12 |
Correct |
616 ms |
15212 KB |
Correct number of moves and valid reconstruction |
| 13 |
Correct |
672 ms |
17900 KB |
Correct number of moves and valid reconstruction |
| 14 |
Correct |
625 ms |
15340 KB |
Correct number of moves and valid reconstruction |
