题目：http://uoj.ac/problem/152

orzKPM。。。

分治，把数字是l~mid的拿出来放在一根柱子上，mid+1~r放在另一根柱子上。如此递归下去，每次递归只是改一下方向，l，r。然后只要处理r-l<=1的情况就可以了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define rep(i,l,r) for (int i=l;i<=r;i++)#define down(i,l,r) for (int i=l;i>=r;i--)#define clr(x,y) memset(x,y,sizeof(x))#define maxn 1000500#define ll long long#define inf int(1e9)using namespace std;int ansx[maxn],ansy[maxn],a[3][maxn],N[3];int tot;int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f;}void move(int x,int y){ ansx[++tot]=x+1,ansy[tot]=y+1; a[y][++N[y]]=a[x][N[x]--];}void dfs(int x,int l,int r,int dir){ if (l==r) return; if (r-l<=1){ if ((dir==0&&a[x][N[x]-1]
            
             a[x][N[x]])){ move(x,(x+1)%3); move(x,(x+2)%3); move((x+1)%3,x); move((x+2)%3,x); } return; } int mid=(l+r)/2; int y=(x+1)%3,z=(x+2)%3; rep(i,l,r) if (a[x][N[x]]<=mid) move(x,y); else move(x,z); dfs(y,l,mid,1-dir); dfs(z,mid+1,r,1-dir); if (dir==0){ down(i,r,mid+1) move(z,x); down(i,mid,l) move(y,x); } else { rep(i,l,mid) move(y,x); rep(i,mid+1,r) move(z,x); }}int main(){ int n=read(); down(i,n,1) a[0][i]=read(); N[0]=n; dfs(0,1,n,0); printf("%d\n",tot); rep(i,1,tot) printf("%d %d\n",ansx[i],ansy[i]); return 0;}