Cod sursa(job #33690)

Utilizator MariusMarius Stroe Marius Data 19 martie 2007 17:54:38
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const char iname[] = "zone.in";
const char oname[] = "zone.out";

typedef long long i64;

#define MAX_N 513

int N;

i64 V[9];  int mark[9];

i64 A[MAX_N][MAX_N];

int l1, l2, c1, c2;


void read_in(void)
{
	freopen(iname, "r", stdin);
	
	scanf("%d", & N);
	for (int i = 0; i < 9; ++ i)
		scanf("%lld", V + i);
	for (int i = 1; i <= N; ++ i)
		for (int j = 1; j <= N; ++ j) {
			scanf("%lld", A[i] + j);
			A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
		}
}

int finds(void)
{
	i64 sum[9];
	sum[0] = A[l1][c1];
	sum[1] = A[l1][c2] - sum[0];
	sum[2] = A[l1][N] - sum[0] - sum[1];
	sum[3] = A[l2][c1] - sum[0];
	sum[4] = A[l2][c2] - sum[0] - sum[1] - sum[3];
	sum[5] = A[l2][N] - sum[0] - sum[1] - sum[2] - sum[3] - sum[4];
	sum[6] = A[N][c1] - sum[0] - sum[3];
	sum[7] = A[N][c2] - sum[0] - sum[1] - sum[3] - sum[4] - sum[6];
	sum[8] = A[N][N] - sum[0] - sum[1] - sum[2] - sum[3] - sum[4] - sum[5] - sum[6] - sum[7];
	sort(sum, sum + 9);
	for (int i = 0; i < 9; ++ i)
		if (sum[i] != V[i])	  return 0;
	return 1;
}

int zone3(void)
{
	for (int i = 0; i < 9; ++ i) {
		if (mark[i] == 0) {
			int stp = 9;
			for (l2 = l1 + 1; stp > 0; stp /= 2) {
				if ((l2 + stp < N) && (A[l2 + stp][c1] - A[l1][c1] <= V[i]))
					l2 = l2 + stp;
			}
			if (A[l2][c1] - A[l1][c1] == V[i])
				if (finds())
					return 1;
		}
	}
	return 0;
}

int zone2(void)
{
	for (int i = 0; i < 9; ++ i) {
		if (mark[i] == 0) {
			int stp = 9;
			for (c2 = c1 + 1; stp > 0; stp /= 2) {
				if ((c2 + stp < N) && (A[l1][c2 + stp] - A[l1][c1] <= V[i]))
					c2 = c2 + stp;
			}
			if (A[l1][c2] - A[l1][c1] == V[i]) {
				mark[i] = 1;
				if (zone3())
					return 1;
				mark[i] = 0;
			}
		}
	}
	return 0;
}

void zone1(void)
{
	for (l1 = 1; l1 < N - 1; ++ l1) {
		for (int i = 0; i < 9; ++ i) {
			int stp = 9;
			for (c1 = 1; stp > 0; stp /= 2) {
				if ((c1 + stp < N - 1) && (A[l1][c1 + stp] <= V[i]))
					c1 = c1 + stp;
			}
			if (A[l1][c1] == V[i]) {
				mark[i] = 1;
				if (zone2()) {
					freopen(oname, "w", stdout);
					printf("%d %d %d %d\n", l1, l2, c1, c2);
					return ;
				}
				mark[i] = 0;
			}
		}
	}
}

int main(void)
{
	read_in();
	sort(V, V + 9);
	zone1();
	return 0;
}