Cod sursa(job #851873)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 10 ianuarie 2013 16:16:56
Problema Zone Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<fstream>
#define DIM 550

using namespace std;

ifstream f("zone.in");
ofstream g("zone.out");

int n;

int c1,c2,l1,l2,ok_t;
int N[20],V[DIM][DIM],Fr[20];

void read(){
	int i,j;
	f>>n;
	
	for(i=1;i<=9;i++)
		f>>N[i];
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			f>>V[i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			V[i][j]+=(V[i-1][j]+V[i][j-1]-V[i-1][j-1]);
}

int validate(){
	int sum1=V[l2][c2]-V[l2][c1]-V[l1][c2]+V[l1][c1];
	int sum2=V[l2][n]-V[l2][c2]-V[l1][n]+V[l1][c2];
	int sum3=V[n][c2]-V[n][c1]-V[l2][c2]+V[l2][c1];
	int sum4=V[n][n]-V[n][c2]-V[l2][n]+V[l2][c2];
	
	int i,ok1,ok2,ok3,ok4;
	
	for(i=1;i<=9;i++){
		if(Fr[i]==0&&N[i]==sum1){
			ok1=1;Fr[i]=1;break;
		}
	}
	for(i=1;i<=9;i++){
		if(Fr[i]==0&&N[i]==sum2){
			ok2=1;Fr[i]=1;break;
		}
	}
	for(i=1;i<=9;i++){
		if(Fr[i]==0&&N[i]==sum3){
			ok3=1;Fr[i]=1;break;
		}
	}
	for(i=1;i<=9;i++){
		if(Fr[i]==0&&N[i]==sum4){
			ok4=1;Fr[i]=1;break;
		}
	}
	return ok1&&ok2&&ok3&&ok4;
}


void find_l2(){
	int sum_t=V[n][c1]-V[l1][c1];
	int sum1,sum2;
	int i,j,st,dr,mid,ok=1;
	for(i=1;i<=9;i++){
		if(Fr[i]==0){
			Fr[i]=1;
			sum1=N[i];ok=1;
			st=l1+1;dr=n-1;
			
			while(st<=dr&&ok){
				mid=(st+dr)/2;
				sum2=V[mid][c1]-V[l1][c1];
				if(sum2==sum1){
					for(j=1;j<=9;j++)
						if(Fr[j]==0&&(N[j]==sum_t-sum2)){
							Fr[j]=1;l2=mid;
							if(validate()){
								g<<l1<<" "<<l2<<" "<<c1<<" "<<c2;
								ok_t=1;
								return;
							}
							ok=0;
							Fr[j]=0;
							break;
						}
				}
				else{
					if(sum2>sum1)
						dr=mid-1;
					else
						st=mid+1;
				}
			}
			Fr[i]=0;
		}
	}
}

void find_c2(){
	int sum_t=V[l1][n]-V[l1][c1];
	int sum1,sum2,ok;
	int i,j,st,dr,mid;
	for(i=1;i<=9;i++){
		if(Fr[i]==0){
			Fr[i]=1;
			sum1=N[i];ok=1;
			st=c1+1;dr=n-1;
			
			while(st<=dr&&ok){
				mid=(st+dr)/2;
				sum2=V[l1][mid]-V[l1][c1];
				if(sum2==sum1){
					for(j=1;j<=9;j++)
						if(Fr[j]==0&&N[j]==(sum_t-sum1)){
							Fr[j]=1;
							c2=mid;
							find_l2();
							if(ok_t)
								return;
							ok=0;
							Fr[j]=0;
							break;
						}
				}
				else{
					if(sum2>sum1)
						dr=mid-1;
					else
						st=mid+1;
				}
			}
			
			Fr[i]=0;
		}
	}
}


void find_c1(){
	
	int st,dr;
	int mid,sum;
	for(int i=1;i<=9;i++){
		Fr[i]=1;
		sum=N[i];st=1;dr=n-1;
		while(st<=dr){
			mid=(st+dr)/2;
			if(V[l1][mid]==sum){
				c1=mid;
				find_c2();
				if(ok_t)
					return;
				break;
			}
			else{
				if(V[l1][mid]>sum)
					dr=mid-1;
				else
					st=mid+1;
			}
			
		}
		Fr[i]=0;
	}
	
}


int main(){
	
	read();
	
	for(l1=1;l1<n&&(ok_t==0);l1++)
		find_c1();
	
	return 0;
}