Cod sursa(job #2147119)

Utilizator robx12lnLinca Robert robx12ln Data 28 februarie 2018 14:43:29
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include<bits/stdc++.h>
using namespace std;
FILE * fin = fopen("zone.in", "r");
FILE * fout = fopen("zone.out", "w");
int N, st, dr, mid;
long long S[515][515], Sum[15], V[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;
}