Cod sursa(job #23456)

Utilizator wefgefAndrei Grigorean wefgef Data 28 februarie 2007 19:43:51
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define mp make_pair
#define pb push_back

#define Nmax 512

pair< pair<int, int>, pair<int, int> > sol;
int A[Nmax][Nmax];
long long S[Nmax][Nmax];
long long p[10], arie[4];
char viz[10];
int n;

void readdata()
{
	freopen("zone.in", "r", stdin);
	freopen("zone.out", "w", stdout);
	
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= 9; ++i)
		scanf("%lld", &p[i]);
	for (i = 1; i <= n; ++i)
	for (j = 1; j <= n; ++j)
		scanf("%d", &A[i][j]);
}

int cauta1(int st, int dr, int ref, int lin, long long val)
{
	int m;
	
	while (st != dr)
	{
		m = (st+dr)/2;
		if (S[lin][m] - S[lin][ref] < val) st = m+1;
		else dr = m;
	}
	if (S[lin][st] - S[lin][ref] == val) return st;
	return -1;
}

int cauta2(int st, int dr, int ref, int lin, long long val)
{
	int m;
	
	while (st != dr)
	{
		m = (st+dr)/2;
		if (S[m][lin] - S[ref][lin] < val) st = m+1;
		else dr = m;
	}
	if (S[st][lin] - S[ref][lin] == val) return st;
	return -1;
}

int valid(int l1, int c1, int l2, int c2)
{
	int i;
	vector<long long> aux, v;
	
	v.clear();
	for (i = 1; i <= 9; ++i) v.pb(p[i]);
	sort(v.begin(), v.end());
	aux.clear();
	aux.pb( S[l1][c1] );
	aux.pb( S[l2][c1]-S[l1][c1] );
	aux.pb( S[n][c1]-S[l2][c1] );
	aux.pb( S[l1][c2]-S[l1][c1] );
	aux.pb( S[l1][n]-S[l1][c2] );
	aux.pb( S[l2][c2]-S[l2][c1]-S[l1][c2]+S[l1][c1] );
	aux.pb( S[n][c2]-S[n][c1]-S[l2][c2]+S[l2][c1] );
	aux.pb( S[l2][n]-S[l2][c2]-S[l1][n]+S[l1][c2] );
	aux.pb( S[n][n]-S[n][c2]-S[l2][n]+S[l2][c2] );
	sort(aux.begin(), aux.end());
	return aux == v;
}

void eval()
{
	int i, j, k, l;
	for (i = 1; i < n-1; ++i)
	{
		j = cauta1(1, n-2, 0, i, arie[1]);
		if (j == -1) continue;
		k = cauta1(j+1, n-1, j, i, arie[2]);
		if (k == -1) continue;
		l = cauta2(i+1, n-1, i, j, arie[3]);
		
		if (valid(i, j, l, k) && mp( mp(i, j), mp(l, k) ) < sol)
			sol = mp( mp(i, j), mp(l, k) );
	}
}

void back(int k)
{
	if (k == 4)
	{
		eval();
		return;
	}
	for (int i = 1; i <= 9; ++i)
		if (!viz[i])
		{
			viz[i] = 1;
			arie[k] = p[i];
			back(k+1);
			viz[i] = 0;
		}
}

void solve()
{
	int i, j;
	
	sol = mp( mp(n, n), mp(n, n) );
	
	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];
		
	back(1);
	printf("%d %d %d %d\n", sol.first.first, sol.second.first, sol.first.second, sol.second.second);
}

int main()
{
	readdata();
	solve();
	return 0;
}