Cod sursa(job #358425)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 23 octombrie 2009 00:12:22
Problema Zone Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <stdio.h>
#define Nmax 520

long long A[Nmax][Nmax], B[Nmax][Nmax], v[15], viz[15], v2[15];
long long n, i, j, l, k, L1, L2, C1, C2, aux, ok, aaa, bbb, ij;

FILE * g = fopen ("zone.out","w");

int binara(long long suma, int indice){
	
	long long st=1;
	long long dr=n;
	long long mj, a, b, c, x;
	
	if (indice==1) 
		while (st <= dr) {
		
		mj = st+(dr-st)/2;
		
		x = B[L1][mj];
		
		if (x < suma)
			st = mj+1;
		
		else 
			if (x > suma)
				dr = mj-1;
			
			else 
				return mj;
	}
	
	if (indice==2) 
		
		while (st <= dr) {
		
		mj = st+(dr-st)/2;
		
		x = B[mj][C1] - B[L1][C1];
		
		if (x < suma)
			st = mj+1;
		
		else 
			if (x > suma)
				dr = mj-1;
			
			else 
				return mj;
	}
	
	if (indice==3) 
	
		while (st <= dr) {
		
			mj = st+(dr-st)/2;
		
			x = B[L2][mj] - B[L2][C1] - B[L1][mj] + B[L1][C1];
		
			if (x < suma)
				st = mj+1;
		
			else 
				if (x > suma)
					dr = mj-1;
				
				else 
					return mj;
		}

return 0;	
}

void preprocesare(){
	
	for (i = 1 ; i <= n ; i++)
		for (j = 1 ; j <= n ; j++)
			
			B[i][j] = A[i][j] + B[i-1][j] + B[i][j-1] - B[i-1][j-1];

}


int impartire(){
	
	for (i = 1 ; i <= n ; i++){
		
		L1 = i;
		
		for (j = 1 ; j <= 9 ; j++){
			
			C1 = binara(v[j],1);
			
			for (l = 1 ; l <= 9 ; l++){
				
				L2 = binara(v[l],2);
				
				for (k = 1 ; k <= n ; k++){
					
					C2 = binara(v[k],3);
					
					v2[1]=B[L1][C1];
					v2[2]=B[L2][C1] - B[L1][C1];
					v2[3]=B[L2][C2] - B[L2][C1] - B[L1][C2] + B[L1][C1];
					v2[4]=B[L1][C2] - B[L1][C1];
					v2[5]=B[L1][n] - B[L1][C2];
					v2[6]=B[L2][n] - B[L2][C2] - B[L1][n] + B[L1][C2];
					v2[7]=B[n][C1] - B[L2][C1];
					v2[8]=B[n][C2] - B[n][C1] - B[L2][C2] + B[L2][C1];
					v2[9]=B[n][n] - B[n][C2] - B[L2][n] + B[L2][C2];
					
					for (aaa = 1 ; aaa < 9 ; aaa++)
						for (bbb = aaa+1 ; bbb <= 9 ; bbb++)
							if (v2[bbb]<v2[aaa]) {
								aux=v2[aaa];
								v2[aaa]=v2[bbb];
								v2[bbb]=aux;
							}
					
					
					
					
					ok = 1;
					for (ij = 1 ; ij <= 9 ; ij++)
						if (v[ij] != v2[ij]) ok = 0;
					
					if (ok==1) return 0;
				}
			}
		}
	}
	
	return 0;
}


int main(){
	
	FILE * f = fopen("zone.in","r");
	
	
	fscanf (f, "%d" , &n);
	for (i = 1 ; i <= 9 ; i++)
		fscanf(f , "%d" , &v[i]);
	
	for (i = 1 ; i < 9 ; i++)
		for ( j = i + 1 ; j <= 9 ; j++) 
			if ( v[i] > v[j] ){
				aux = v[i];
				v[i] = v[j];
				v[j] = aux;
			}
	

	for (i = 1 ; i <= n ; i++)
		for (j = 1 ; j <= n ; j++)
			fscanf (f, "%d", &A[i][j]);

	preprocesare();
	
	impartire();
	
	fprintf(g , "%ld " , L1);
	fprintf(g , "%ld " , L2);
	fprintf(g , "%ld " , C1);
 	fprintf(g , "%ld" , C2);
	
	fclose(f);
	fclose(g);
	return 0;
}