Cod sursa(job #552123)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 11 martie 2011 18:00:24
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define DIM 514
#define INF (1 << 28) - 1

ifstream f ("zone.in");
ofstream g ("zone.out");

int N, A[DIM][DIM], P[DIM][DIM], S[11], R[11], V[11], L1, L2, C1, C2, X1, X2, Y1, Y2;

int cauta (int val, int sw)
{
	int p, u, m;
	switch (sw)
	{
		case 1:
			p = 1, u = N - 2;
			break;
		case 2:
			p = L1 + 1, u = N - 1;
			break;
		case 3:
			p = C1 + 1, u = N - 1;
			break;		
	}
	while (p <= u)
	{
		m = (p + u) >> 1;
		switch (sw)
		{
			case 1:
				if (P[L1][m] <= val)
					p = m + 1;
				else
					u = m - 1;
				
				break;
			case 2:
				if (P[m][C1] - P[L1][C1] <= val)
					p = m + 1;
				else
					u = m - 1;
				
				break;
			case 3:
				if (P[L1][m] - P[L1][C1] <= val)
					p = m + 1;
				else
					u = m - 1;
				
				break;		
		}		
	}
	switch (sw)
	{
		case 1:
			sw = P[L1][u] == val ? u : 0;
			break;
		case 2:
			sw = P[u][C1] - P[L1][C1] == val ? u : 0;
			break;
		case 3:
			sw = P[L1][u] - P[L1][C1] == val ? u : 0;
			break;
	}
	return sw;
}

int cmp ()
{
	for (int i = 1; i <= 9; i++)
		if (S[i] != R[i])
			return 0;
	if (X2 <= L2)
		return 0;
	if (X1+X2+Y1+Y2 <= L1+L2+C1+C2)
		return 0;
	return 1;
	
}

int second ()
{
	int s1, s2, s3;
	for (L1 = 1; L1 < N - 1; L1++)
		for (s1 = 1; s1 <= 9; s1++)
			if (!V[s1])
			{
				C1 = cauta (S[s1], 1);
				if (C1 == 0)
					continue;
				
				V[s1] = 1;				
				for (s2 = 1; s2 <= 9; s2++)
					if (!V[s2])
					{
						L2 = cauta (S[s2], 2);
						if (L2 == 0)
							continue;
						
						V[s2] = 1;
						for (s3 = 1; s3 <= 9; s3++)
							if (!V[s3])
							{
								C2 = cauta (S[s3], 3);
								if (C2 == 0)
									continue;
								
								R[1] = S[s1], R[2] = S[s2], R[4] = S[s3];
								R[3] = P[N][C1] - R[1] - R[2]; 
								R[5] = P[L2][C2] - R[1] - R[2] - R[4];
								R[6] = P[N][C2] - R[1] - R[2] - R[3] - R[4] - R[5];
								R[7] = P[L1][N] - R[1] - R[4];
								R[8] = P[L2][N] - R[1] - R[2] - R[4] - R[5] - R[7]; 
								R[9] = P[N][N] - R[1] - R[2] - R[3] - R[4] - R[5] - R[6] - R[7] - R[8]; 
								sort (R + 1, R + 10);
								if ( cmp () )
								{
									X1 = L1, X2 = L2;
									Y1 = C1, Y2 = C2;
								}
							}						
						V[s2] = 0;
					}					
				V[s1] = 0;
			}
}

int main (){
	int i, j;
	
	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];			
		}
	X1 = X2 = Y1 = Y2 = INF;
	second ();
	g << X1 << ' ' << X2 << ' ' << Y1 << ' ' << Y2;
	return 0;
}