Pagini recente » Cod sursa (job #3273352) | Cod sursa (job #1255986) | Cod sursa (job #1504464) | Cod sursa (job #1774384) | Cod sursa (job #552123)
Cod sursa(job #552123)
#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;
}