Cod sursa(job #1757264)

Utilizator Athena99Anghel Anca Athena99 Data 14 septembrie 2016 19:23:52
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("zone.in");
ofstream fout("zone.out");

typedef long long i64;

const int nmax= 512;

bool u[9];

i64 v[9], v2[9], s[nmax+1][nmax+1];

i64 sum( int i1, int j1, int i2, int j2 ) {
    return (i64)s[i2][j2]-s[i2][j1-1]-s[i1-1][j2]+s[i1-1][j1-1];
}

int main(  ) {
    int n, n2;
    fin>>n;
    for ( n2= 1; n2*2<=n; n2*= 2 ) ;
    for ( int i= 0; i<9; ++i ) {
        fin>>v[i];
    }
    sort( v, v+9 );
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=n; ++j ) {
            fin>>s[i][j];
            s[i][j]= s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }

    int l1= 0, l2= 0, c1= 0, c2= 0;
    for ( int i1= 1; i1<=n-2; ++i1 ) {
        for ( int j1= 0; j1<9; ++j1 ) {
            int x1= 0;
            for ( int step= n2; step>0; step/= 2 ) {
                if ( x1+step<=n-2 && s[i1][x1+step]<=v[j1] ) {
                    x1+= step;
                }
            }

            if ( s[i1][x1]==v[j1] ) {
                u[j1]= 1;
                for ( int j2= 0; j2<9; ++j2 ) {
                    if ( u[j2]==0 ) {
                        int x2= 0;
                        for ( int step= n2; step>0; step/= 2 ) {
                            if ( x2+step<=n-1 && s[i1][x2+step]-v[j1]<=v[j2] ) {
                                x2+= step;
                            }
                        }

                        if ( s[i1][x2]-v[j1]==v[j2] ) {
                            u[j2]= 1;
                            for ( int j3= 0; j3<9; ++j3 ) {
                                if ( u[j3]==0 ) {
                                    u[j3]= 1;
                                    int i2= 0;
                                    for ( int step= n2; step>0; step/= 2 ) {
                                        if ( i2+step<=n-1 && s[i2+step][x1]-s[i1][x1]<=v[j3] ) {
                                            i2+= step;
                                        }
                                    }

                                    v2[0]= sum(1, 1, i1, x1);
                                    v2[1]= sum(1, x1+1, i1, x2);
                                    v2[2]= sum(1, x2+1, i1, n);
                                    v2[3]= sum(i1+1, 1, i2, x1);
                                    v2[4]= sum(i1+1, x1+1, i2, x2);
                                    v2[5]= sum(i1+1, x2+1, i2, n);
                                    v2[6]= sum(i2+1, 1, n, x1);
                                    v2[7]= sum(i2+1, x1+1, n, x2);
                                    v2[8]= sum(i2+1, x2+1, n, n);
                                    sort( v2, v2+9 );

                                    int aux= 0;
                                    for ( int i= 0; i<9; ++i ) {
                                        if ( v[i]==v2[i] ) {
                                            ++aux;
                                        }
                                    }
                                    if ( aux==9 && l1==0 ) {
                                        l1= i1, l2= i2, c1= x1, c2= x2;
                                    }

                                    u[j3]= 0;
                                }
                            }

                            u[j2]= 0;
                        }
                    }
                }

                u[j1]= 0;
            }
        }
    }

    fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";

    return 0;
}