Yes you are right, i just asked if there is a tricky part on this problem
My method is find cycles and put them on an array
and to the middle of the array swap the begining and the end
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXN 6000
int N,array[2*MAXN],place[2*MAXN],used[2*MAXN],cur=0,list[20][2*MAXN][6],last[2*MAXN];
void change(int x,int y)
{
if(used[x] || used[y]) return;
if(x==y) { used[x]=1; return;}
/* printf("%d with %d\n",x,y);
*/ int xx=array[x],yy=array[y];
array[x]=yy; place[yy]=x;
array[y]=xx; place[xx]=y;
used[x]=used[y]=1;
list[cur][last[cur]][0]=x;
list[cur][last[cur]++][1]=y;
}
int main()
{
int i,j,ctrl;
scanf(" %d",&N);
for(i=1;i<=N;i++)
{
scanf(" %d",&array[i]);
place[array[i]]=i;
}
int listx[MAXN*2],lastx,x,y;
while(1)
{
ctrl=1;
for(i=1;i<=N;i++) if(array[i]!=i) {ctrl=0; break;}
if(ctrl) break;
/* for(i=1;i<=N;i++) printf("%d ",array[i]); printf("\n");
*/
for(i=1;i<=N;i++)
{
if(!used[i] && array[i]!=i)
{
lastx=0;
listx[lastx++]=i;
while(1)
{
x=array[listx[lastx-1]];
if(x!=i)
{
listx[lastx++]=x;
}
else break;
}
x=0;
y=lastx-1;
/* for(j=lastx-1;j>=0;j--) listx[j+1]=listx[j];
listx[0]=listx[lastx];
*/
while(x<=y)
{
change(listx[x],listx[y]);
x++; y--;
}
}
}
for(i=1;i<=N;i++) used[i]=0;
cur++;
}
printf("%d\n",cur);
for(i=0;i<cur;i++)
{
printf("%d",last[i]);
for(j=0;j<last[i];j++)
printf(" %d-%d",list[i][j][0],list[i][j][1]);
printf("\n");
}
return 0;
}
i always get WA ...