Pagini recente » Cod sursa (job #136732) | Cod sursa (job #3156773) | Cod sursa (job #2969782) | Cod sursa (job #3005206) | Cod sursa (job #2910306)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "zone.in" );
ofstream fout( "zone.out" );
using ll = long long;
const int DIM = 520;
const int NZ = 9;
ll sum[NZ + 1];
int a[DIM][DIM];
ll S[DIM][DIM];
int n;
int l1 = 1e9, c1 = 1e9, l2 = 1e9, c2 = 1e9;
int bsl( ll val, int c ) {
int st = 0, dr = n;
while ( dr - st > 1 ) {
int mid = (st + dr) / 2;
if ( S[mid][c] < val ) {
st = mid;
} else {
dr = mid;
}
}
if ( S[st][c] == val ) return st;
if ( S[dr][c] == val ) return dr;
return -1;
}
int bsc( ll val, int l ) {
int st = 0, dr = n;
while ( dr - st > 1 ) {
int mid = (st + dr) / 2;
if ( S[l][mid] < val ) {
st = mid;
} else {
dr = mid;
}
}
if ( S[l][st] == val ) return st;
if ( S[l][dr] == val ) return dr;
return -1;
}
void solve( int x, int y, int z, int zl1 ) {
// x = zona 1 , y = zona 2, z = zona 4
int zc1 = bsc( sum[x], zl1 );
if ( zc1 == -1 ) return;
int zl2 = bsl( sum[x] + sum[z], zc1 );
int zc2 = bsc( sum[x] + sum[y], zl1 );
if ( zl1 == -1 || zl2 == -1 || zc1 == -1 || zc2 == -1 ) return;
vector<int> q(NZ + 1);
q[1] = S[zl1][zc1];
q[2] = S[zl1][zc2] - S[zl1][zc1];
q[3] = S[zl1][n] - S[zl1][zc2];
q[4] = S[zl2][zc1] - S[zl1][zc1];
q[5] = S[zl2][zc2] - q[1] - q[2] - q[4];
q[6] = S[zl2][n] - q[1] - q[2] - q[3] - q[4] - q[5];
q[7] = S[n][zc1] - S[zl2][zc1];
q[8] = S[n][zc2] - q[1] - q[2] - q[4] - q[5] - q[7];
q[9] = S[n][n] - q[1] - q[2] - q[3] - q[4] - q[5] - q[6] - q[7] - q[8];
sort( q.begin(), q.end() );
for ( int i = 1; i <= NZ; ++i ) {
if ( q[i] != sum[i] ) return;
}
if ( l1 > zl1 ) {
l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
} else if ( l1 == zl1 ) {
if ( c1 > zc1 ) {
l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
} else if ( c1 == zc1 ) {
if ( l2 > zl2 ) {
l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
} else if ( l2 == zl2 ) {
if ( c2 > zc2 ) {
l1 = zl1, l2 = zl2, c1 = zc1, c2 = zc2;
}
}
}
}
}
int main() {
fin >> n;
for ( int i = 1; i <= NZ; ++i ) fin >> sum[i];
sort(sum + 1, sum + NZ + 1);
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= n; ++j ) {
fin >> a[i][j];
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j];
}
}
for ( int i = 1; i <= n; ++i ) {
for ( int x = 1; x <= NZ; ++x ) {
for ( int y = 1; y <= NZ; ++y ) {
if ( x == y ) continue;
for ( int z = 1; z <= NZ; ++z ) {
if ( x == z || y == z ) continue;
solve(x, y, z, i);
}
}
}
}
fout << l1 << " " << l2 << " " << c1 << " " << c2 << "\n";
fin.close();
fout.close();
return 0;
}