Cod sursa(job #355392)

Utilizator Addy.Adrian Draghici Addy. Data 10 octombrie 2009 22:36:02
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <stdio.h>
#include <algorithm>
#define DIM 520

using namespace std;

int A[DIM][DIM];
long long S[DIM][DIM], suma[12], T[12], viz[12];
long long n, i, j, t, p, u, m, ok, k;
int L1, L2, C1, C2;

int cautaC1() {
	p = 1, u = n-2;
	while (p <= u) {
		m = (u-p)/2 + p;
		if (S[L1][m] == suma[i]) {
			C1 = m;
			viz[i] = 1;
			return 1;
		}
		else
			if (S[L1][m] < suma[i])
				p = m+1;
			else
				u = m-1;
	}
	return 0;
}

int cautaL2() {
	p = L1+1, u = n-1;
	while (p <= u) {
		m = (u-p)/2 + p;
		if (S[m][C1] - S[L1][C1] == suma[j]) {
			L2 = m;
			viz[j] = 1;
			return 1;
		}
		else
			if (S[m][C1] - S[L1][C1] < suma[j])
				p = m+1;
			else
				u = m-1;
	}
	return 0;
}

int cautaC2() {
	p = C1+1, u = n-1;
	while (p <= u) {
		m = (u-p)/2 + p;
		if (S[L1][m] - S[L1][C1] == suma[t]) {
			C2 = m;
			viz[t] = 1;
			return 1;
		}
		else
			if (S[L1][m] - S[L1][C1] < suma[t])
				p = m+1;
			else
				u = m-1;
	}
	return 0;
}

int verif() {
	int i, ok;
	ok = 1, k = 0;
	T[1] = S[L1][n] - S[L1][C2];
	T[2] = S[L2][C2] - S[L2][C1] - S[L1][C2] + S[L1][C1];
	T[3] = S[L2][n] - S[L1][n] - S[L2][C2] + S[L1][C2];
	T[4] = S[n][C1] - S[L2][C1];
	T[5] = S[n][C2] - S[n][C1] - S[L2][C2] + S[L2][C1];
	T[6] = S[n][n] - S[n][C2] - S[L2][n] + S[L2][C2];
	sort(T+1, T+7);
	for (i = 1; i <= 9; i++)
		if (!viz[i])
			if (suma[i] != T[++k])
				ok = 0;
	if (ok)
		return 1;
	else
		return 0;
}

int main() {
	
	FILE *f = fopen("zone.in", "r");
	FILE *g = fopen("zone.out", "w");
	
	fscanf(f, "%lld", &n);	
	for (i = 1; i <= 9; i++)
		fscanf(f, "%lld", &suma[i]);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			fscanf(f, "%d", &A[i][j]);
	
	sort(suma+1, suma+10);
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
	
	for (L1 = 1; L1 <= n-2 && !ok; L1++) {
		for (i = 1; i <= 9 && !ok; i++) {
			if (cautaC1()) {
				for (j = 1; j <= 9 && !ok; j++) {
					if (!viz[j])
						if (cautaL2()) {
							for (t = 1; t <= 9 && !ok; t++) {
								if (!viz[t])
									if (cautaC2()) {
										if (verif()) {
											ok = 1;
											fprintf(g, "%d %d %d %d", L1, L2, C1, C2);
										}
										viz[t] = 0;
									}
							}
							viz[j] = 0;
						}
				}
				viz[i] = 0;
			}
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}