Pagini recente » Cod sursa (job #2654141) | Cod sursa (job #2356090) | Cod sursa (job #3242071) | Cod sursa (job #2370067) | Cod sursa (job #359424)
Cod sursa(job #359424)
//O(N*log^3 de constanta 9^3)
#include <stdio.h>
#include <algorithm>
#define DIM 530
using namespace std;
long long S[DIM][DIM];
long long A[DIM][DIM];
long long D[12];
long long V[12];
long long R[12];
long long T[12];
long long N,i,j,k,s1,s2,s3,ok,p,u;
int L1,L2,C1,C2;
int main(){
FILE *f = fopen("zone.in","r");
fscanf(f,"%lld",&N);
for (i=1;i<=9;i++)
fscanf(f,"%lld",&D[i]);
sort(D+1,D+10);
for (i=1;i<=N;i++)
for (j=1;j<=N;j++) {
fscanf(f,"%lld",&A[i][j]);
S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j];
}
fclose(f);
for (L1 = 1;L1<=N-2;L1++) {
for (s1 = 1;s1<=9;s1++) {
p=1;u=N-2;
while (p<=u) {
C1 = (p+u)/2;
if (S[L1][C1] == D[s1])
break;
if (S[L1][C1]<D[s1])
p = C1+1;
else
u = C1-1;
}
if (p<=u) {
//am fixat L1 si C1, incerc sa fixez pe L2
V[s1] = 1;
for (s2 = 1;s2<=9;s2++)
if (V[s2]!=1) {
p = L1+1;
u = N-1;
while (p<=u) {
L2 = (p+u)/2;
if (D[s2] == S[L2][C1] - S[L1][C1])
break;
if (D[s2] > S[L2][C1] - S[L1][C1])
p = L2+1;
else
u = L2-1;
}
if (p<=u) {
//am fixat L1, C1, L2, incerc sa fixez C2
V[s2] = 1;
for (s3=1;s3<=9;s3++)
if (V[s3]!=1) {
p = C1+1;
u = N-1;
while (p<=u) {
C2 = (p+u)/2;
if (D[s3] == S[L1][C2]-S[L1][C1])
break;
if (D[s3] > S[L1][C2]-S[L1][C1])
p = C2+1;
else
u = C2-1;
}
if (p<=u) {
V[s3] = 1;
//am fixat cele 4 si am calculat 3 arii
for (i=1,k=0;i<=9;i++)
if (V[i] == 0)
R[++k] = D[i];
T[1] = S[L2][C2] - S[L2][C1] - S[L1][C2] + S[L1][C1];
T[2] = S[N][C1] - S[L2][C1];
T[3] = S[L1][N] - S[L1][C2];
T[4] = S[N][C2] - S[N][C1] - S[L2][C2] + S[L2][C1];
T[5] = S[L2][N] - S[L1][N] - S[L2][C2] + S[L1][C2];
T[6] = S[N][N] - S[N][C2] - S[L2][N] + S[L2][C2];
sort(T+1,T+7);
ok = 1;
for (i=1;i<=6;i++)
if (R[i]!=T[i])
ok = 0;
if (ok) {
FILE *g = fopen("zone.out","w");
fprintf(g,"%d %d %d %d",L1,L2,C1,C2);
fclose(g);
return 0;
} else {
V[s3] = 0;
}
}
}
V[s2] = 0;
}
}
V[s1] = 0;
}
}
}
return 0;
}