Pagini recente » Cod sursa (job #2328567) | Cod sursa (job #586119) | Cod sursa (job #388717) | Cod sursa (job #1117049) | Cod sursa (job #33680)
Cod sursa(job #33680)
#include <cstdio>
#include <algorithm>
using namespace std;
const char iname[] = "zone.in";
const char oname[] = "zone.out";
typedef long long i64;
#define MAX_N 512
int N;
i64 V[10]; int mark[10];
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 = 0; i < N; ++ i)
for (int j = 0; j < N; ++ j) {
scanf("%lld", A[i] + j);
if (i == 0 && j > 0)
A[i][j] += A[i][j - 1];
else if (i > 0 && j == 0)
A[i][j] += A[i - 1][j];
else
A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
}
}
int finds(void)
{
i64 sum[10];
sum[0] = A[l1][c1];
sum[1] = A[l1][c2] - sum[0];
sum[2] = A[l1][N - 1] - 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 - 1] - sum[0] - sum[1] - sum[2] - sum[3] - sum[4];
sum[6] = A[N - 1][c1] - sum[0] - sum[3];
sum[7] = A[N - 1][c2] - sum[0] - sum[1] - sum[3] - sum[4] - sum[6];
sum[8] = A[N - 1][N - 1] - 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 = 10;
for (l2 = l1 + 1; stp > 0; stp /= 2) {
if ((l2 + stp < N - 1) && (A[l2 + stp][c1] - A[l1][c1] <= V[i]))
l2 = l2 + stp;
}
if (A[l2][c1] - A[l1][c1] == V[i]) {
mark[i] = 1;
if (finds())
return 1;
mark[i] = 0;
}
}
}
return 0;
}
int zone2(void)
{
for (int i = 0; i < 9; ++ i) {
if (mark[i] == 0) {
int stp = 10;
for (c2 = c1 + 1; stp > 0; stp /= 2) {
if ((c2 + stp < N - 1) && (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 = 0; l1 < N - 2; ++ l1) {
for (int i = 0; i < 9; ++ i) {
int stp = 10;
for (c1 = 0; stp > 0; stp /= 2) {
if ((c1 + stp < N - 2) && (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 + 1, l2 + 1, c1 + 1, c2 + 1);
return ;
}
mark[i] = 0;
}
}
}
}
int main(void)
{
read_in();
sort(V, V + 9);
zone1();
return 0;
}