Pagini recente » Cod sursa (job #2335992) | Cod sursa (job #1784893) | Cod sursa (job #1343392) | Clasament simulare_oji2012_clasele_11-12 | Cod sursa (job #553909)
Cod sursa(job #553909)
#include<stdio.h>
#include<algorithm>
#define maxN 515
#define Inf 1 << 28
#define i64 long long
using namespace std;
FILE*f=fopen("zone.in","r");
FILE*g=fopen("zone.out","w");
int L1,L2,C1,C2,N,i,j,p,u,Viz[11],m,A[maxN][maxN];
i64 S[maxN][maxN],V[11],W[11];
int LF1,LF2,CF1,CF2;
int s1,s2,s3;
int cbC1 () {
p = 1 ; u = N - 2;
while ( p <= u ){
m = p + ( u - p ) / 2;
if ( S[L1][m] == V[s1] )
return m;
if ( S[L1][m] < V[s1] )
p = m + 1;
else
u = m - 1;
}
return 0;
}
int cbL2 () {
p = L1 + 1; u = N - 1;
while ( p <= u ){
m = p + ( u - p ) / 2;
if ( S[m][C1] - S[L1][C1] == V[s2] )
return m;
if ( S[m][C1] - S[L1][C1] < V[s2] )
p = m + 1;
else
u = m - 1;
}
return 0;
}
int cbC2 () {
p = C1 + 1; u = N - 1;
while ( p <= u ){
m = p + ( u - p ) / 2;
if ( S[L1][m] - S[L1][C1] == V[s3] )
return m;
if ( S[L1][m] - S[L1][C1] < V[s3] )
p = m + 1;
else
u = m - 1;
}
return 0;
}
void Solutie () {
W[1] = V[s1]; W[4] = V[s2]; W[2] = V[s3];
W[3] = S[L1][N] - W[1] - W[2]; W[5] = S[L2][C2] - W[1] - W[2] - W[4];
W[6] = S[L2][N] - W[5] - W[4] - W[3] - W[2] - W[1];
W[7] = S[N][C1] - W[4] - W[1]; W[8] = S[N][C2] - W[1] - W[2] - W[4] - W[5] - W[7];
W[9] = S[N][N] - W[1] - W[2] - W[3] - W[4] - W[5] - W[6] - W[7] - W[8] ;
sort(W+1,W+10);
int ok = 0;
for ( int i = 1 ; i <= 9 ; ++i ){
if ( V[i] != W[i] )
ok = 1;
}
if ( !ok ){
if ( LF1+LF2+CF1+CF2 > L1 + L2 + C1 + C2 )
LF1 = L1,LF2= L2,CF1 = C1,CF2 = C2;
}
}
int main () {
fscanf(f,"%d",&N);
for ( i = 1 ; i <= 9 ; ++i ){
fscanf(f,"%lld",&V[i]);
}
sort(V+1,V+10);
for ( i = 1 ; i <= N ; ++i ){
for ( j = 1 ; j <= N ; ++j ){
fscanf(f,"%d",&A[i][j]);
}
}
for ( i = 1 ; i <= N ; ++i ){
for ( j = 1 ; j <= N ; ++j ){
S[i][j] = S[i-1][j] + S[i][j-1] + A[i][j] - S[i-1][j-1];
}
}
LF1 = Inf;
for ( L1 = 1 ; L1 < N - 1 ; ++L1 ){
for ( s1 = 1 ; s1 <= 9 ; ++s1 ){
if ( !Viz[s1] ){
if ( C1 = cbC1() ){
Viz[s1] = 1;
for ( s2 = 1 ; s2 <= 9 ; ++s2 ){
if ( !Viz[s2] ){
if ( L2 = cbL2() ){
Viz[s2] = 1;
for ( s3 = 1 ; s3 <= 9 ; ++s3 ){
if ( !Viz[s3] ){
if ( C2 = cbC2() ){
Solutie();
}
}
}
Viz[s2] = 0;
}
}
}
Viz[s1] = 0;
}
}
}
}
fprintf(g,"%d %d %d %d\n",LF1,LF2,CF1,CF2);
fclose(f);
fclose(g);
return 0;
}