Cod sursa(job #553322)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 13 martie 2011 21:43:38
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include<stdio.h>
#include<algorithm>
#define maxN 515
#define Inf 1 << 28
#define i64 long long
using namespace std;

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

int L1,L2,C1,C2,N,Nr,i,j,p,u,Viz[11];
i64 S[maxN][maxN],V[11],W[11];
int LF1,LF2,CF1,CF2;
int s1,s2,s3;

int cautbin1 (i64 val){
	int m;
	p = 1; u = N - 2;
	
	while ( p <= u ){
		m = (p + u) >> 1; 
		if ( S[L1][ m ] == val )
			return m;
		if ( S[L1][ m ] < val )
			p = m + 1;
		else
			u = m - 1;
		
	}
	return 0;
}

int cautbin2 ( i64 val ){
	int m;
	p = C1 + 1; u = N - 1;
	
	while ( p <= u ){
		m = (p + u) >> 1; 
		if ( S[L1][m] - S[L1][C1] == val )
			return m;
		if ( S[L1][m] - S[L1][C1] < val )
			p = m + 1;
		else
			u = m - 1;
	}
	return 0;
	
}

int cautbin3 ( i64 val ){
	int m;
	p = L1 + 1; u = N - 1;
	
	while ( p <= u ){
		m = (p + u) >> 1; 
		if ( S[m][C1] - S[L1][C1] == val )
			return m;
		if ( S[m][C1] - S[L1][C1] < val )
			p = m + 1;
		else
			u = m - 1;
	}		
	return 0;
	
}

int cmp () {
	for ( int i = 1 ; i <= 9 ; ++i ){
		if ( V[i] != W[i] )
			return 0;
	}
	return 1;
}

void Solutie () {
	W[1] = S[L1][C1]; W[2] = S[L1][C2] - S[L1][C1]; W[3] = S[L1][N] - S[L1][C2]; 
	W[4] = S[L2][C1] - S[L1][C1]; W[5] = S[L2][C2] - S[L2][C1] - S[L1][C2] + S[L1][C1];
	W[6] = S[L2][N] - S[L2][C2] - S[L1][N] + S[L1][C2]; W[7] = S[N][C1] - S[L2][C1];
	W[8] = S[N][C2] - S[N][C1] - S[L2][C2] + S[L2][C1]; 
	W[9] = S[N][N] - S[N][C2] - S[L2][N] + S[L2][C2];
	
	sort(W+1,W+10);
	
	if ( cmp() ) {
		if ( LF1 + LF2 + CF1 + CF2 > L1 + C1 + L2 + C2 ){
			LF1 = L1 ; LF2 = L2 ; CF1 = C1; CF2 = C2;
		}
	}
	
}

void solve () {
	
	for ( L1 = 1 ; L1 < N - 1 ; ++L1 ){
		for ( s1 = 1 ; s1 <= 9 ; ++s1 ){
			
			C1 = cautbin1( V[s1] );
			if ( !C1 )	continue ;
			Viz[s1] = 1;
			
			for ( s2 = 1 ; s2 <= 9 ; ++s2 ){
				if ( Viz[s2] )	continue ;
				
				C2 = cautbin2( V[s2] );
				if ( !C2 )	continue;
				Viz[s2] = 1;
				
				for ( s3 = 1 ; s3 <= 9 ; ++s3 ){
					if ( Viz[s3] )	continue ;
					L2 = cautbin3( V[s3] );
					if ( !L2 )	continue ;
					
					Solutie();
				}
				Viz[s2] = 0;
			}
			Viz[s1] = 0;
		}
		
	}
	
}

int main () {
	fscanf(f,"%d",&N);
	
	for ( i = 1 ; i <= 9 ; ++i ){
		fscanf(f,"%d",&V[i]);
	}
	sort(V+1,V+10);
	
	for ( i = 1 ; i <= N ; ++i ){
		for ( j = 1 ; j <= N ; ++j ){
			fscanf(f,"%lld",&Nr);
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + Nr;
		}
	}
	
	LF1 = LF2 = CF1 = CF2 = Inf;
	
	solve() ;
	
	fprintf(g,"%d %d %d %d\n",LF1,LF2,CF1,CF2);
	
	fclose(f);
	fclose(g);
	
	return 0;
}