Cod sursa(job #358497)

Utilizator dexter_dexMutascu Adrian - Dragos dexter_dex Data 23 octombrie 2009 15:14:40
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <stdio.h>
#include<algorithm>
#define Nmax 520

using namespace std;


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, 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++){
				
				if (j != l)
					L2 = binara(v[l],2);
				
				for (k = 1 ; k <= 9 ; k++){
					
					if (j != k && l != 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];
					
					sort (v2+1,v2+10);
					
					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, "%lld" , &n);
	for (i = 1 ; i <= 9 ; i++)
		fscanf(f , "%lld" , &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, "%lld", &A[i][j]);

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