Cod sursa(job #862400)

Utilizator CS-meStanca Marian Ciprian CS-me Data 22 ianuarie 2013 17:56:28
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *fin=fopen("zone.in","r");
FILE *fout=fopen("zone.out","w");

int n,v[11],x[10],y[10],a[514][514],l1,l2,c1,c2,val,p,u,ok,s;


int apartine(int s){
	for(int i = 1; i<=9; i++){
		if(s==v[i]){
			return i;
		}
	}
return -1;	
}
int verificare(int l1, int l2, int c1, int c2){
	int u;
	u=0;
	for(int i = 1 ; i<=9; i++){
		if(v[i]>0){
			x[++u]=v[i];
		}
	}
	y[1]=a[l1][n]-a[l1][c2];
	y[2]=a[l2][c2]-a[l2][c1]-a[l1][c2]+a[l1][c1];
	y[3]=a[l2][n]-a[l2][c2]-a[l1][n]+a[l1][c2];
	y[4]=a[n][c1]-a[l2][c1];
	y[5]=a[n][c2]-a[n][c1]-a[l2][c2]+a[l2][c1];
	y[6]=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
	
	sort(x+1,x+7);
	sort(y+1,y+7);
	
	for(int i = 1; i<=6; i++){
		if(x[i]!=y[i]){
			return 0;
		}
	}
	
	fprintf(fout,"%d %d %d %d",l1,l2,c1,c2);
	
return 1;
}
int main(){
	
	fscanf(fin,"%d",&n);
	
	for(int i = 1; i<=9; i++){
		fscanf(fin,"%d",&v[i]);
	}
	
	sort(v+1,v+10);
	
	for(int i = 1; i<=n; i++){
		for(int j = 1; j<=n; j++){
			fscanf(fin,"%d",&val);
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+val;
		}
	}
	
	for(int l1 = 1; l1<=n-1; l1++){
		
		for(int s1 = 1; s1<=9; s1++){
			
			p=1;
			u=n;
			ok=0;
			while(p<=u){
				c1=(p+u)/2;
				
				s=a[l1][c1];
				if(s==v[s1]){
					ok=1;
					break;
				}
				if(s<v[s1]){
					p=c1+1;
				}
				else{
					u=c1-1;
				}
			}
			
			if(ok==1){
				v[s1]=-v[s1];
				
				p=l1+1;
				u=n;
				ok=0;
				
				for(int s2=1;s2<=9; s2++){
					
					p=l1+1;
					u=n;
					ok=0;
					while(p<=u){
						l2=(p+u)/2;
						
						s=a[l2][c1]-a[l1][c1];
						
						if( s==v[s2] ){
							ok=1;
							break;
						}
						if(s<v[s2]){
							p=l2+1;
						}
						else{
							u=l2-1;
						}
						
					}
					
					if(ok==1){
						v[s2]=-v[s2];
						
						for(int s3=1; s3<=9; s3++){
							
							p=c1+1;
							u=n;
							ok=0;
							
							while(p<=u){
								
								c2=(p+u)/2;
								s=a[l1][c2]-a[l1][c1];
								
								if(s==v[s3]){
									v[s3]=-v[s3];
									ok=verificare(l1,l2,c1,c2);
									v[s3]=-v[s3];
									if(ok) return 0;
									break;
								}
								if(s<v[s3]){
									p=c2+1;
								}
								else{
									u=c2-1;
								}
								
							}
							
							
							
							
						}// for s3
						
						
						v[s2]=-v[s2];
					}
					
				}// for s2
				
				v[s1]=-v[s1];
			}
			
		}// for s1
		
		
	}
	
	
	return 0;
}