Cod sursa(job #354803)

Utilizator bixcabc abc bixc Data 9 octombrie 2009 16:16:15
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
//O(N*log^3 de constanta 9^3)
#include <stdio.h>
#include <algorithm>
#define DIM 530

using namespace std;

long long S[DIM][DIM];
long long A[DIM][DIM];

long long D[12];
long long V[12];
long long R[12];
long long T[12];

long long N,i,j,k,s1,s2,s3,ok,p,u;
int L1,L2,C1,C2;

int main(){
	FILE *f = fopen("zone.in","r");
	fscanf(f,"%lld",&N);
	for (i=1;i<=9;i++)
		fscanf(f,"%lld",&D[i]);
	sort(D+1,D+10);
	for (i=1;i<=N;i++)
		for (j=1;j<=N;j++) {
			fscanf(f,"%lld",&A[i][j]);
			S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j];
		}
	fclose(f);
	
	for (L1 = 1;L1<=N-2;L1++) {
		for (s1 = 1;s1<=9;s1++) {
			p=1;u=N-2;
			while (p<=u) {
				C1 = (p+u)/2;
				if (S[L1][C1] == D[s1]) 
					break;
				if (S[L1][C1]<D[s1])
					p = C1+1;
				else
					u = C1-1;
			}
			if (p<=u) {
				//am fixat L1 si C1, incerc sa fixez pe L2
				V[s1] = 1;
				for (s2 = 1;s2<=9;s2++)
					if (V[s2]!=1) {
						p = L1+1;
						u = N-1;
						while (p<=u) {
							L2 = (p+u)/2;
							if (D[s2] == S[L2][C1] - S[L1][C1])
								break;
							if (D[s2] > S[L2][C1] - S[L1][C1])
								p = L2+1;
							else
								u = L2-1;
						}
						if (p<=u) {
							//am fixat L1, C1, L2, incerc sa fixez C2
							V[s2] = 1;
							for (s3=1;s3<=9;s3++)
								if (V[s3]!=1) {
									p = C1+1;
									u = N-1;
									while (p<=u) {
										C2 = (p+u)/2;
										if (D[s3] == S[L1][C2]-S[L1][C1])
											break;
										if (D[s3] > S[L1][C2]-S[L1][C1])
											p = C2+1;
										else
											u = C2-1;
									}
									if (p<=u) {
										V[s3] = 1;
										//am fixat cele 4 si am calculat 3 arii
										for (i=1,k=0;i<=9;i++) 
											if (V[i] == 0)
												R[++k] = D[i];
										T[1] = S[L2][C2] - S[L2][C1] - S[L1][C2] + S[L1][C1];
										T[2] = S[N][C1] - S[L2][C1];
										T[3] = S[L1][N] - S[L1][C2];
										T[4] = S[N][C2] - S[N][C1] - S[L2][C2] + S[L2][C1];
										T[5] = S[L2][N] - S[L1][N] - S[L2][C2] + S[L1][C2];
										T[6] = S[N][N] - S[N][C2] - S[L2][N] + S[L2][C2];
										sort(T+1,T+7);
										ok = 1;
										for (i=1;i<=6;i++)
											if (R[i]!=T[i])
												ok = 0;
										if (ok) {
											FILE *g = fopen("zone.out","w");
											fprintf(g,"%d %d %d %d",L1,L2,C1,C2);
											fclose(g);
											return 0;
										} else {
											V[s3] = 0;
										}
									}
								}
							V[s2] = 0;
						}
					}
				V[s1] = 0;
			}
		}
	}

	return 0;
}