2015年1月29日 星期四

2015/01/29 Codeforces 489A. SwapSort

// http://codeforces.com/contest/489/problem/A
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef pair<int, int> xi;

#define x first
#define i second

int N;
xi A[4000];
int rev[4000];

vector<int> Ans;

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

    for(int Ni = 0; Ni < N; Ni++)
    {
        scanf("%d", &A[Ni].x);
        A[Ni].i = Ni;
    }

    sort(A, A+N);

    for(int Ni = 0; Ni < N; Ni++)
        rev[A[Ni].i ] = Ni;

    for(int Ni = 0; Ni < N; Ni++)
    {
        while( A[Ni].i != Ni )
        {
            Ans.push_back(A[Ni].i );
            Ans.push_back(Ni);

            int p = A[Ni].i;

            A[Ni].i = Ni;
            A[rev[Ni] ].i = p;

            int t = rev[Ni];

            rev[Ni] = Ni;
            rev[p] = t;
        }
    }

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

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

沒有留言:

張貼留言