Pagini recente » Cod sursa (job #1179120) | Cod sursa (job #875788) | Cod sursa (job #1047113) | Cod sursa (job #3155574) | Cod sursa (job #33686)
Cod sursa(job #33686)
#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;
int V[10]; int mark[10];
int A[MAX_N][MAX_N];
int l1, l2, c1, c2;
void read_in(void)
{
freopen(iname, "r", stdin);
int i;
int j;
scanf("%d", & N);
for (i = 0; i < 9; ++ i)
scanf("%d", V + i);
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j) {
scanf("%d", A[i] + j);
A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
}
}
int finds(void)
{
int sum[10];
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)
{
freopen(oname, "w", stdout);
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()) {
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;
}