Cod sursa(job #204937)

Utilizator mordredSimionescu Andrei mordred Data 28 august 2008 13:00:32
Problema Grozavesti Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#define min(a,b) ((a>b)?b:a)
#define nmax 1000002

int n,i,j,k,a[1000][1000],min,x,y,m,sc[20000],aux;
int in_ordine(){
for(i=1;i<n;++i)if(a[i][i]>a[i+1][i+1])return i; return 0;}

int main(){
 freopen("grozavesti.in","r",stdin);
 freopen("grozavesti.out","w",stdout);
 
 scanf("%d",&n);
 
 for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
        scanf("%d",&a[i][j]);
 
 for(i=1;i<=n-1;++i)
    {
    min = a[i][i];x=y=0;
    for(j=i;j<=n;++j) 
        for(k=i;k<=n;++k)
            if(a[j][k]<=min&&a[j][k]>a[i-1][i-1])
                min=a[j][k],x=j,y=k;
    if(x&&y)
        {
        if(y!=i){
        sc[++m]=1,
        sc[++m]=i,
        sc[++m]=y;
        for(j=1;j<=n;++j){aux=a[j][i];a[j][i]=a[j][y];a[j][y]=aux;}
        }
        if(x!=i){
        sc[++m]=0,
        sc[++m]=i,
        sc[++m]=x;
        for(j=1;j<=n;++j){aux=a[i][j];a[i][j]=a[x][j];a[x][j]=aux;}
        }
        }
    }
 
 i=in_ordine();
 while(i){
    sc[++m]=1;
    sc[++m]=i;
    sc[++m]=i+1;
    sc[++m]=0;
    sc[++m]=i;
    sc[++m]=i+1;
    aux=a[i][i];a[i][i]=a[i+1][i+1];a[i+1][i+1]=aux;
    i=in_ordine();
    }
    
  printf("%d\n",m/3);
 for(i=1;i<=m;++i)
    {
    if(i%3==1)printf((sc[i])?"C ":"L ");
    else if(i%3==2)printf("%d ",sc[i]);
    else printf("%d\n",sc[i]);
    }
/*
 printf("\n");
 for(i=1;i<=n;++i){
    for(j=1;j<=n;++j)
        printf("%5d ",a[i][j]);printf("\n");}
        printf("\n\n");
        for(i=1;i<=n;i++)
            printf("%5d ", a[i][i]);printf("\n%d",in_ordine());*/
 
 return 0;
}