Pagini recente » Cod sursa (job #1342898) | Profil SeekHunt1334 | Cod sursa (job #1871435) | Cod sursa (job #17151) | Cod sursa (job #552663)
Cod sursa(job #552663)
#include <fstream>
#include <algorithm>
using namespace std;
#define DIM 514
ifstream f ("zone.in");
ofstream g ("zone.out");
int N, A[DIM][DIM], P[DIM][DIM], S[11], R[11], T[12], L1, L2, C1, C2, K[11], e;
int p,u;
int k1,k2,k3,ok;
int i,j;
int main (){
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];
}
for( L1=1 ; L1<=N-2 ; L1++ ){
for( k1=1 ; k1 <= 9 ; k1++){
p=1;
u=N-2;
while(p<=u){
C1=(u+p)/2;
if(P[L1][C1]==S[k1])
break;
if(P[L1][C1]>S[k1])
u=C1-1;
else
p=C1+1;
}
if(p<=u){
K[k1]=1;
for(k2=1;k2<=9;k2++)
if(K[k2]==0){
p=L1+1;
u=N-1;
while(p<=u){
L2=(p+u)/2;
if(P[L2][C1]-P[L1][C1]==S[k2])
break;
if(P[L2][C1]-P[L1][C1]>S[k2])
u=L2-1;
else
p=L2+1;
}
if(p<=u){
K[k2]=1;
for(k3=1;k3<=9;k3++)
if(K[k3]==0){
p=C1+1;
u=N-1;
while(p<=u){
C2=(p+u)/2;
if(P[L1][C2]-P[L1][C1]==S[k3])
break;
if(P[L1][C2]-P[L1][C1]>S[k3])
u=C2-1;
else
p=C2+1;
}
if(p<=u){
K[k3]=1;
for(i=1,e=0;i<=9;i++)
if(K[i]==0)
T[++e] = S[i];
R[1] = P[L2][C2] - P[L2][C1] - P[L1][C2] + P[L1][C1];
R[2] = P[N][C1] - P[L2][C1];
R[3] = P[L1][N] - P[L1][C2];
R[4] = P[N][C2] - P[N][C1] - P[L2][C2] + P[L2][C1];
R[5] = P[L2][N] - P[L1][N] - P[L2][C2] + P[L1][C2];
R[6] = P[N][N] - P[N][C2] - P[L2][N] + P[L2][C2];
sort(R+1,R+7);
sort(T+1,T+7);
ok=1;
for(i=1;i<=6;i++)
if(R[i]!=T[i]){
ok=0;
break;
}
if(ok){
g<<L1<<" "<<L2<<" "<<C1<< " "<<C2;
return 0;
}
else
K[k3]=0;
}
}
K[k2]=0;
}
}
K[k1]=0;
}
}
}
return 0;
}