Cod sursa(job #330303)

Utilizator Andrei200Andrei200 Andrei200 Data 9 iulie 2009 14:55:19
Problema Grozavesti Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


#define file_in "grozavesti.in"
#define file_out "grozavesti.out"

#define Nmax 310

struct g
{
	char c;
	int ind1,ind2;
}s[2*Nmax];

struct g1
{
	int x1,y1;
}ss[Nmax*Nmax];

int n,ok,nr,nrsol;
int a[Nmax][Nmax];
int v[Nmax*Nmax];
int nrm=0;

void qsort(long l, long r)   
{   
 long i,j,x,y;   
 i=l;   
 j=r;   
 x=v[(l+r)>>1];   
 do  
    {   
    while ((v[i]<x)&&(i<nr)) ++i;   
    while ((x<v[j])&&(j>1)) --j;   
    if (i<=j)   
        {   
        y=v[i];   
        v[i]=v[j];   
        v[j]=y; 
       
		y=ss[i].x1;   
       	ss[i].x1=ss[j].x1;   
        ss[j].x1=y;
       
		y=ss[i].y1;   
        ss[i].y1=ss[j].y1;   
        ss[j].y1=y;		
        ++i;   
        --j;   
        }   
    }   
 while (i<=j);   
 if (l<j) qsort(l,j);   
 if (i<r) qsort(i,r);   
}   


int bun()
{
	int i;
	for (i=2;i<=n;++i)
		 if (a[i][i]<a[i-1][i-1]) return 0;
	return 1;
}

int main()
{
	int i,j,x;
	freopen(file_in,"r",stdin);
	
	scanf("%d", &n);
	nr=0;
	memset(v,0,sizeof(v));
	for (i=1;i<=n;++i)
		 for (j=1;j<=n;++j)
		 {
			 scanf("%d", &a[i][j]);
			 nr++;
			 v[nr]=a[i][j];
			 ss[nr].x1=i;
			 ss[nr].y1=j;			 
		 }
	fclose(stdin);	 

    nrsol=0;
	
	for (x=1;x<=n && !bun();++x)
	{
		ok=0;
		for (i=1;i<=n && !ok;++i)
			 if (v[x]==a[i][i])
             {
	          ok=1;
			  a[i][i]=0;
			 }
		     else
			 {
				ok=1;
				if (a[x][x]>a[i][j])
				{
				nrsol++;
				s[nrsol].c='C';   
                s[nrsol].ind1=x;   
                s[nrsol].ind2=i;
				}
				else
				{
				nrsol++;
				s[nrsol].c='L';   
                s[nrsol].ind1=x;   
                s[nrsol].ind2=i;
				}
			 }
	}
	

	
	
    freopen(file_out,"w",stdout);
	printf("%d\n", nrsol);
	for (i=1;i<=nrsol;++i)
		 printf("%c %d %d\n", s[i].c,s[i].ind1,s[i].ind2);

	fclose(stdout);

	return 0;
}