Pagini recente » Cod sursa (job #1761532) | Cod sursa (job #1165025) | Cod sursa (job #1794371) | Cod sursa (job #724259) | Cod sursa (job #2147118)
#include<bits/stdc++.h>
using namespace std;
FILE * fin = fopen("zone.in", "r");
FILE * fout = fopen("zone.out", "w");
int N, S[515][515], V[15], st, dr, mid, Sum[15];
pair< pair<int,int>, pair<int,int> > Sol;
inline bool check( int L1, int L2, int C1, int C2 ){
Sum[1] = S[L1][C1];
Sum[2] = S[L1][C2] - S[L1][C1];
Sum[3] = S[L1][N] - S[L1][C2];
Sum[4] = S[L2][C1] - S[L1][C1];
Sum[5] = S[L2][C2] - ( Sum[1] + Sum[2] + Sum[4] );
Sum[6] = S[L2][N] - ( Sum[1] + Sum[2] + Sum[3] + Sum[4] + Sum[5] );
Sum[7] = S[N][C1] - S[L2][C1];
Sum[8] = S[N][C2] - ( Sum[1] + Sum[2] + Sum[4] + Sum[5] + Sum[7] );
Sum[9] = S[N][N] - ( Sum[1] + Sum[2] + Sum[3] + Sum[4] + Sum[5] + Sum[6] + Sum[7] + Sum[8] );
sort( Sum + 1, Sum + 10 );
for( int i = 1; i <= 9; i++ )
if( V[i] != Sum[i] )
return false;
return true;
}
int main(){
fscanf( fin, "%d", &N );
Sol.first.first = Sol.first.second = Sol.second.first = Sol.second.second = N;
for( int i = 1; i <= 9; i++ )
fscanf( fin, "%d", &V[i] );
for( int i = 1; i <= N; i++ )
for( int j = 1; j <= N; j++ )
fscanf( fin, "%d", &S[i][j] );
for( int i = 1; i <= N; i++ )
for( int j = 1; j <= N; j++ )
S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
sort( V + 1, V + 10 );
for( int L1 = 1; L1 <= N; L1++ ){
for( int P1 = 1; P1 <= 9; P1++ ){
int C1 = 0;
st = 1;
dr = N;
while( st <= dr ){
mid = ( st + dr ) / 2;
if( S[L1][mid] == V[P1] ){
C1 = mid;
break;
}
if( S[L1][mid] < V[P1] )
st = mid + 1;
else
dr = mid - 1;
}
if( C1 == 0 )
continue;
for( int P4 = 1; P4 <= 9; P4++ ){
if( P4 == P1 )
continue;
int L2 = 0;
st = L1 + 1;
dr = N;
while( st <= dr ){
mid = ( st + dr ) / 2;
if( S[mid][C1] - S[L1][C1] == V[P4] ){
L2 = mid;
break;
}
if( S[mid][C1] - S[L1][C1] < V[P4] )
st = mid + 1;
else
dr = mid - 1;
}
if( L2 == 0 )
continue;
for( int P2 = 1; P2 <= 9; P2++ ){
if( P2 == P1 || P2 == P4 )
continue;
int C2 = 0;
st = C1 + 1;
dr = N;
while( st <= dr ){
mid = ( st + dr ) / 2;
if( S[L1][mid] - S[L1][C1] == V[P2] ){
C2 = mid;
break;
}
if( S[L1][mid] - S[L1][C1] < V[P2] )
st = mid + 1;
else
dr = mid - 1;
}
if( C2 == 0 )
continue;
if( check( L1, L2, C1, C2 ) == true )
Sol = min( Sol, { {L1, C1},{L2, C2} } );
}
}
}
}
fprintf( fout, "%d %d %d %d\n", Sol.first.first, Sol.second.first, Sol.first.second, Sol.second.second );
return 0;
}