Cod sursa(job #25955)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 4 martie 2007 16:51:37
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define nmax 515

int l1,l2,c1,c2,n,i,j,lo,hi,mid,k;
long long s[10],a[nmax][nmax],ss[10],x;

int numeric (const void *p1, const void *p2)
{
	return (*(int*)p1)-(*(int*)p2);
}

int ok()
{
	ss[0]=a[l1][c1],ss[1]=a[l1][c2]-a[l1][c1],ss[2]=a[l1][n]-a[l1][c2];
	ss[3]=a[l2][c1]-a[l1][c1],ss[4]=a[l2][c2]-a[l2][c1]-a[l1][c2]+a[l1][c1],ss[5]=a[l2][n]-a[l2][c2]-a[l1][n]+a[l1][c2];
	ss[6]=a[n][c1]-a[l2][c1],ss[7]=a[n][c2]-a[n][c1]-a[l2][c2]+a[l2][c1],ss[8]=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
	qsort((void*)ss,9,sizeof(ss[0]),numeric);
	for (int i=0;i<9;i++)
		if (s[i]!=ss[i])
			return 0;
	printf("%d %d %d %d\n",l1,l2,c1,c2);
	return 1;
}

int main()
{
	freopen("zone.in","r",stdin);
	freopen("zone.out","w",stdout);

	scanf("%d",&n);
	for (i=0;i<9;i++)
		scanf("%lld",s+i);
	qsort((void*)s,9,sizeof(s[0]),numeric);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			scanf("%lld",&x),a[i][j]=x+a[i][j-1]+a[i-1][j]-a[i-1][j-1];

	for (l1=1;l1<n-1;++l1)
	{
		for (i=0;i<9;i++)
		{
			int key=s[i];
			int *itemptr=(int *)bsearch(&key,a[l1],n,sizeof(int),numeric);
			if (itemptr)
			{
				c1=itemptr-a[l1];
				for (j=0;j<9;j++)
				{
					int key2=key+s[j];
					lo=l1+1,hi=n-1;
					while (lo!=hi)
					{
						mid=(lo+hi)/2;
						if (a[mid][c1]<key2)
							lo=mid+1;
						else
							hi=mid;
					}
					if (a[lo][c1]==key2)
					{
						l2=lo;
						for (k=0;k<9;k++)
						{
							int key3=key+s[k];
							lo=c1+1,hi=n-1;
							while (lo!=hi)
							{
								mid=(lo+hi)/2;
								if (a[l1][mid]<key3)
									lo=mid+1;
								else
									hi=mid;
							}
							if (a[l1][lo]==key3)
							{
								c2=lo;
								if (ok())
									return 0;
							}
						}
					}
				}
			}
		}
	}

	return 0;
}