2015年2月6日 星期五

2013-2014 ACM ICPC Central European Regional Contest (CERC 13), problem: (I) Crane

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

vector<int> Ans;
int A[20000];
int pos[20000];

int T, N;

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &N);
        Ans.clear();

        for(int Ni = 1; Ni <= N; Ni++)
        {
            scanf("%d", &A[Ni]);
            pos[A[Ni] ] = Ni;
        }

        for(int Ni = N; Ni >= 1; Ni--)
        {
            while( pos[Ni] != Ni )
            {
                int st, n;

                if( pos[Ni]*2 <= Ni ) st = 1, n = pos[Ni];
                else st = pos[Ni]*2-Ni+1, n = Ni-pos[Ni];

                Ans.push_back(st);
                Ans.push_back(min(pos[Ni]*2, Ni) );

                //int n = pos[Ni];

                for(int i = 0; i < n; i++)
                {
                    swap(pos[A[st+i] ], pos[A[st+i+n] ]);
                    swap(A[st+i], A[st+i+n]);
                }

                //printf("OAO %d %d\n", Ni, pos[Ni]);
            }
        }

        printf("%d\n", Ans.size()/2);

        for(int Ai = 0; Ai < Ans.size(); Ai += 2)
            printf("%d %d\n", Ans[Ai], Ans[Ai+1]);

    }
}

沒有留言:

張貼留言