#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 qq, int w){
swap(f[qq],f[w]);
swap(f[a-qq+1],f[a-w+1]);
}
void dfs(int qq){
//zx++;
bo[qq]=t;
if(f[qq]<=a/2){
if(bo[f[qq]]==t) return;
dfs(f[qq]);
}else{
zx++;
qi++;q[qi].first=qq;
if(bo[a+1-f[qq]]==t) return;
dfs(a+1-f[qq]);
}
}
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;*/
}
}
sup=qi/2;
if(qi%2==1){
printf("-1\n");
continue;
}else{
//printf("%d 0\n",a);
}
c=0;d=0;e=0;
qqi=0;pi=0;
for(i=1; i<=a/2; i++){
if(bo[i]==t) continue;
e++;
zx=0;
qi=0;
dfs(i);
for(j=1; j<=qi/2; j++){
pi++;
p[pi].first=q[j].first;
p[pi].second=a-q[qi-j+1].first+1;
sw(q[j].first,a-q[qi-j+1].first+1);
}
if(qi%2==1){
qqi++;
qq[qqi].first=q[qi/2+qi%2].first;
}
c+=zx/2;
d+=zx%2;
}
for(i=1; i+1<=qqi; i+=2){
pi++;
p[pi].first=qq[i].first;
p[pi].second=a-qq[i+1].first+1;
//cout<<p[pi].first<<" l "<<p[pi].second<<endl;
sw(qq[i].first,a-qq[i+1].first+1);
}
sup+=a/2-(e+c-d/2);
//sample
for(i=1; i<=a/2; i++){
//cout<<f[i]<<" ";
k[f[i]]=i;
}
//cout<<endl;
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);
}
//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:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
25 | scanf("%d\n",&tes);
| ~~~~~^~~~~~~~~~~~~
cat.cpp:28:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
| ~~~~~^~~~~~~~~~~
cat.cpp:28:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | if(t!=tes) scanf("%d\n",&a); else scanf("%d",&a);
| ~~~~~^~~~~~~~~
cat.cpp:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
31 | if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
| ~~~~~^~~~~~~~~~~~
cat.cpp:31:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
31 | if(i==a) scanf("%d",&f[i]); else scanf("%d ",&f[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
620 KB |
Output is correct |
| 2 |
Correct |
30 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
460 KB |
Output is correct |
| 2 |
Correct |
30 ms |
620 KB |
Output is correct |
| 3 |
Correct |
30 ms |
640 KB |
Output is correct |
| 4 |
Correct |
33 ms |
620 KB |
Output is correct |
| 5 |
Correct |
12 ms |
512 KB |
Output is correct |
| 6 |
Correct |
10 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
620 KB |
Output is correct |
| 2 |
Correct |
30 ms |
640 KB |
Output is correct |
| 3 |
Correct |
629 ms |
13036 KB |
Output is correct |
| 4 |
Correct |
595 ms |
11860 KB |
Output is correct |
| 5 |
Correct |
627 ms |
14476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
460 KB |
Output is correct |
| 2 |
Correct |
30 ms |
620 KB |
Output is correct |
| 3 |
Correct |
30 ms |
640 KB |
Output is correct |
| 4 |
Correct |
33 ms |
620 KB |
Output is correct |
| 5 |
Correct |
12 ms |
512 KB |
Output is correct |
| 6 |
Correct |
10 ms |
492 KB |
Output is correct |
| 7 |
Correct |
629 ms |
13036 KB |
Output is correct |
| 8 |
Correct |
595 ms |
11860 KB |
Output is correct |
| 9 |
Correct |
627 ms |
14476 KB |
Output is correct |
| 10 |
Correct |
627 ms |
11372 KB |
Output is correct |
| 11 |
Correct |
592 ms |
9708 KB |
Output is correct |
| 12 |
Correct |
614 ms |
13292 KB |
Output is correct |
| 13 |
Correct |
657 ms |
14884 KB |
Output is correct |
| 14 |
Correct |
610 ms |
12652 KB |
Output is correct |
