Cod sursa(job #93966)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 21 octombrie 2007 00:11:32
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>

int a[3505][3],n,m;

void construire(int n)
{
	int aux,w,q;
	for (int i=n/2; i>=1; i--)
	{
		w=i;
		q=0;
		while (q!=w && 2*w<=n)
		{
			q=w;
			if (2*w+1<=n && a[2*w][0]<a[w*2+1][0])
			{
				if (a[w][0]<a[2*w+1][0])
				{
					aux=a[w][0];
					a[w][0]=a[2*w+1][0];
					a[w*2+1][0]=aux;
					aux=a[w][1];
					a[w][1]=a[2*w+1][1];
					a[w*2+1][1]=aux;
					aux=a[w][2];
					a[w][2]=a[2*w+1][2];
					a[w*2+1][2]=aux;
					w=w*2+1;
				}
			}
			else
				if (a[w][0]<a[2*w][0])
				{
					aux=a[w][0];
					a[w][0]=a[2*w][0];
					a[w*2][0]=aux;
					aux=a[w][1];
					a[w][1]=a[2*w][1];
					a[w*2][1]=aux;
					aux=a[w][2];
					a[w][2]=a[2*w][2];
					a[w*2][2]=aux;
					w*=2;
				}
		}
	}
}

void extragere()
{
    int aux,e;
	e=n;
	for (int i=1; i<n; i++)
	{
		aux=a[1][0];
		a[1][0]=a[e--][0];
		a[e+1][0]=aux;
		aux=a[1][1];
		a[1][1]=a[e+1][1];
		a[e+1][1]=aux;
		aux=a[1][2];
		a[1][2]=a[e+1][2];
		a[e+1][2]=aux;
		construire(e);
	}
}

void rezolvare()
{
int p=1,z[3];
z[0]=a[1][0];
z[1]=a[1][1];
z[2]=a[1][2];
for (int i=2; i<=n; i++)
    if (a[i][0]>z[0] && a[i][1]>z[1] && a[i][2]>z[2])
       ++p;
printf("%d\n",p);
}

void citire()
{
    freopen("cutii.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (int j=1; j<=m; j++)
    {
	for (int i=1; i<=n; i++)
	    scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
	construire(n);
	extragere();
	rezolvare();
    }
    fclose(stdin);
}

int main()
{
    freopen("cutii.out","w",stdout);
    citire();
    fclose(stdout);
    return 0;
}