Cod sursa(job #552663)

Utilizator Tucu94Andrei Tuculanu Tucu94 Data 12 martie 2011 17:58:16
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define DIM 514
ifstream f ("zone.in");
ofstream g ("zone.out");

int N, A[DIM][DIM], P[DIM][DIM], S[11], R[11], T[12], L1, L2, C1, C2, K[11], e;
int p,u;
int k1,k2,k3,ok;
int i,j;

int main (){
	
	
	f >> N;
	for (i = 1; i <= 9; i++)
		f >> S[i];
	sort (S + 1, S + 10);
	for (i = 1; i <= N; i++)
		for (j = 1; j <= N; j++)
		{
			f >> A[i][j];
			P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];			
		}
	
	
	for( L1=1 ; L1<=N-2 ; L1++ ){
		for( k1=1 ; k1 <= 9 ; k1++){
				p=1;
				u=N-2;
				
				while(p<=u){
					C1=(u+p)/2;
					if(P[L1][C1]==S[k1])
						break;
					if(P[L1][C1]>S[k1])
						u=C1-1;
					else
						p=C1+1;
				}
				if(p<=u){
					K[k1]=1;
					
					for(k2=1;k2<=9;k2++)
						if(K[k2]==0){
							p=L1+1;
							u=N-1;
							
							while(p<=u){
								L2=(p+u)/2;
								if(P[L2][C1]-P[L1][C1]==S[k2])
									break;
								if(P[L2][C1]-P[L1][C1]>S[k2])
									u=L2-1;
								else
									p=L2+1;
							}
							if(p<=u){
								K[k2]=1;
								
								for(k3=1;k3<=9;k3++)
									if(K[k3]==0){
										p=C1+1;
										u=N-1;
										
										while(p<=u){
											C2=(p+u)/2;
											if(P[L1][C2]-P[L1][C1]==S[k3])
												break;
											if(P[L1][C2]-P[L1][C1]>S[k3])
												u=C2-1;
											else
												p=C2+1;
										}
										if(p<=u){
											K[k3]=1;
											for(i=1,e=0;i<=9;i++)
												if(K[i]==0)
													T[++e] = S[i];
											R[1] = P[L2][C2] - P[L2][C1] - P[L1][C2] + P[L1][C1];
											R[2] = P[N][C1] - P[L2][C1];
											R[3] = P[L1][N] - P[L1][C2];
											R[4] = P[N][C2] - P[N][C1] - P[L2][C2] + P[L2][C1];
											R[5] = P[L2][N] - P[L1][N] - P[L2][C2] + P[L1][C2];
											R[6] = P[N][N] - P[N][C2] - P[L2][N] + P[L2][C2];
											sort(R+1,R+7);
											sort(T+1,T+7);
											ok=1;
											for(i=1;i<=6;i++)
												if(R[i]!=T[i]){
													ok=0;
													break;
												}
											if(ok){
												g<<L1<<" "<<L2<<" "<<C1<< " "<<C2;
												return 0;
											}
											else
												K[k3]=0;
										}
									}
							K[k2]=0;		
						}
						
					
					
					
				}
				K[k1]=0;
			}
		}
	}
	
	
	
	return 0;
}