Cod sursa(job #590132)

Utilizator darrenRares Buhai darren Data 15 mai 2011 17:07:13
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdlib>
#include <fstream>
#include <algorithm>

using namespace std;

typedef long long i64;

i64 N, Z[10];
i64 A[515][515];
i64 S[512][512];
i64 Val[10], Sv[10];

inline i64 sum(int i1, int j1, int i2, int j2)
{
	return S[i2][j2] - S[i1 - 1][j2] - S[i2][j1 - 1] + S[i1 - 1][j1 - 1];
}

int main()
{
	ifstream fin("zone.in");
	ofstream fout("zone.out");
	
	fin >> N;
	for (int i = 1; i <= 9; ++i)
		fin >> Z[i];
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
		{
			fin >> A[i][j];
			S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
		}
	
	// 81 * N^2 log^2 N
	
	int step;
	for (step = 1; (step << 1) <= N; step <<= 1);
	
	for (int first = 1; first <= 9; ++first)
		for (int l1 = 1; l1 <= N - 2; ++l1)
		{
			int nstep1 = step,  c1;
			for (c1 = N - 1; nstep1; nstep1 >>= 1)
				if (c1 - nstep1 >= 1 && S[l1][c1 - nstep1] >= Z[first])
					c1 -= nstep1;
			if (c1 == N - 1) continue;
			for (int second = 1; second <= 9; ++second)
				if (first != second)
				{
					Sv[0] = 0;
					for (int k = 1; k <= 9; ++k)
						if (k != first && k != second)
							Sv[++Sv[0]] = Z[k];
					sort(Sv + 1, Sv + Sv[0] + 1);
					
					for (int l2 = l1 + 2; l2 <= N; ++l2)
					{
						int nstep2 = step, c2;
						for (c2 = N + 1; nstep2; nstep2 >>= 1)
							if (c2 - nstep2 >= c1 + 2 && sum(l2, c2 - nstep2, N, N) >= Z[second])
								c2 -= nstep2;
						if (c2 == N + 1) continue;
						
						// Primul si ultimul sunt obtinute sigur
						
						Val[0] = 0;
						Val[++Val[0]] = sum(1, c1 + 1, l1, c2 - 1);
						Val[++Val[0]] = sum(1, c2, l1, N);
						Val[++Val[0]] = sum(l1 + 1, 1, l2 - 1, c1);
						Val[++Val[0]] = sum(l1 + 1, c1 + 1, l2 - 1, c2 - 1);
						Val[++Val[0]] = sum(l1 + 1, c2, l2 - 1, N);
						Val[++Val[0]] = sum(l2, 1, N, c1);
						Val[++Val[0]] = sum(l2, c1 + 1, N, c2 - 1);
						
						sort(Val + 1, Val + Val[0] + 1);
						
						bool ok = true;
						for (int i = 1; i <= Sv[0]; ++i)
							if (Sv[i] != Val[i])
							{
								ok = false;
								break;
							}
						
						if (ok)
						{
							fout << l1 << ' ' << l2 - 1 << ' ' << c1 << ' ' << c2 - 1 << '\n';
							fin.close();
							fout.close();
							exit(0);
						}
					}
				}
		}
	
	fin.close();
	fout.close();
}