Cod sursa(job #551768)

Utilizator ChallengeMurtaza Alexandru Challenge Data 11 martie 2011 08:46:54
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="zone.in";
const char OutFile[]="zone.out";
const int MaxN=600;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,sol_l1=MaxN,sol_l2=MaxN,sol_c1=MaxN,sol_c2=MaxN,l1,c1,l2,c2,s1,s2,s3,used[16];
long long x,zona[16],A[MaxN][MaxN];

inline long long getsum(int l1,int c1,int l2,int c2)
{
	return A[l2][c2]-A[l1-1][c2]-A[l2][c1-1]+A[l1-1][c1-1];
}

inline bool better()
{
	if(l1<sol_l1)
	{
		return true;
	}
	else if(l1==sol_l1)
	{
		if(c1<sol_c1)
		{
			return true;
		}
		else if(c1==sol_c1)
		{
			if(l2<sol_l2)
			{
				return true;
			}
			else if(l2==sol_l2)
			{
				if(c2<sol_c2)
				{
					return true;
				}
			}
		}
	}
	return false;
}

inline bool is_sol()
{
	long long buffer[16];
	buffer[1]=getsum(1,1,l1,c1);
	buffer[2]=getsum(1,c1+1,l1,c2);
	buffer[3]=getsum(1,c2+1,l1,N);
	buffer[4]=getsum(l1+1,1,l2,c1);
	buffer[5]=getsum(l1+1,c1+1,l2,c2);
	buffer[6]=getsum(l1+1,c2+1,l2,N);
	buffer[7]=getsum(l2+1,1,N,c1);
	buffer[8]=getsum(l2+1,c1+1,N,c2);
	buffer[9]=getsum(l2+1,c2+1,N,N);
	sort(buffer+1,buffer+10);
	for(register int i=1;i<=9;++i)
	{
		if(buffer[i]!=zona[i])
		{
			return false;
		}
	}
	return true;
}

inline int cauta_c1()
{
	int st=1;
	int dr=N;
	while(st<=dr)
	{
		int m=st+((dr-st)>>1);
		long long s=getsum(1,1,l1,m);
		if(s==zona[s1])
		{
			return m;
		}
		else if(s<zona[s1])
		{
			st=m+1;
		}
		else
		{
			dr=m-1;
		}
	}
	return 0;
}

inline int cauta_c2()
{
	int st=c1+1;
	int dr=N;
	while(st<=dr)
	{
		int m=st+((dr-st)>>1);
		long long s=getsum(1,c1+1,l1,m);
		if(s==zona[s2])
		{
			return m;
		}
		else if(s<zona[s2])
		{
			st=m+1;
		}
		else
		{
			dr=m-1;
		}
	}
	return 0;
}

inline int cauta_l2()
{
	int st=l1+1;
	int dr=N;
	while(st<=dr)
	{
		int m=st+((dr-st)>>1);
		long long s=getsum(l1+1,1,m,c1);
		if(s==zona[s3])
		{
			return m;
		}
		else if(s<zona[s3])
		{
			st=m+1;
		}
		else
		{
			dr=m-1;
		}
	}
	return 0;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=9;++i)
	{
		fin>>zona[i];
	}
	sort(zona+1,zona+10);
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			fin>>x;
			A[i][j]=x+A[i-1][j]+A[i][j-1]-A[i-1][j-1];
		}
	}
	fin.close();
	
	for(l1=1;l1<=N-2;++l1)
	{
		for(s1=1;s1<=9;++s1)
		{
			used[s1]=1;
			c1=cauta_c1();
			if(c1)
			{
				for(s2=1;s2<=9;++s2)
				{
					if(used[s2]==0)
					{
						used[s2]=1;
						c2=cauta_c2();
						if(c2)
						{
							for(s3=1;s3<=9;++s3)
							{
								if(used[s3]==0)
								{
									used[s3]=1;
									l2=cauta_l2();
									if(l2)
									{
										if(is_sol())
										{
											if(better())
											{
												sol_l1=l1;
												sol_l2=l2;
												sol_c1=c1;
												sol_c2=c2;
											}
										}
									}
									used[s3]=0;
								}
							}
						}
						used[s2]=0;
					}
				}
			}
			used[s1]=0;
		}
	}	

	fout<<sol_l1<<" "<<sol_l2<<" "<<sol_c1<<" "<<sol_c2;
	fout.close();
	return 0;
}