Cod sursa(job #1059747)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 decembrie 2013 21:58:38
Problema Grozavesti Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <algorithm>

#define maxn 310

using namespace std;

ifstream fin("grozavesti.in");
ofstream fout("grozavesti.out");

struct field
{
    int x,i,j;
}v[maxn*maxn];

int row[maxn],col[maxn];
int invrow[maxn],invcol[maxn];
char s[maxn*2];
int sol1[maxn*2],sol2[maxn*2];
int n,t;

bool cmp (const field &a, const field &b)
{
    return a.x < b.x;
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
    {
        ++t;
        fin>>v[t].x;
        v[t].i = i;
        v[t].j = j;
    }

    for (int i=1; i<=n; ++i)
    {
        row[i] = i;
        invrow[i] = i;
        col[i] = i;
        invcol[i] = i;
    }

    sort (v+1,v+t+1,cmp);
    t=0;

    for (int i=1,j=1; i<=n; ++i)
    {
        while (row[v[j].i] < i || col[v[j].j] < i) ++j;

        if (row[v[j].i] != i)
        {
            ++t;
            s[t] = 'L';
            sol1[t] = row[v[j].i];
            sol2[t] = i;
            int temp = row[v[j].i];
            swap (row[v[j].i],row[invrow[i]]);
            swap (invrow[temp],invrow[i]);
        }

        if (col[v[j].j] != i)
        {
            ++t;
            s[t] = 'C';
            sol1[t] = col[v[j].j];
            sol2[t] = i;
            int temp = col[v[j].j];
            swap (col[v[j].j],col[invcol[i]]);
            swap (invcol[temp],invcol[i]);
        }
    }

    fout<<t<<"\n";

    for (int i=1; i<=t; ++i)
    {
        fout<<s[i]<<" "<<sol1[i]<<" "<<sol2[i]<<"\n";
    }
}