Cod sursa(job #566727)

Utilizator DraStiKDragos Oprica DraStiK Data 29 martie 2011 11:25:50
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <algorithm>
using namespace std;

#define DIM 515
#define LIM 10

long long sum[DIM][DIM];
long long v[LIM];
int N;

void read ()
{
    int i,j,x;

    scanf ("%d",&N);
    for (i=1; i<LIM; ++i)
        scanf ("%lld",&v[i]);
    sort (v+1,v+LIM);

    for (i=1; i<=N; ++i)
        for (j=1; j<=N; ++j)
        {
            scanf ("%d",&x);
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
        }
}

inline int caut_bin_x (long long val,int x,int st,int dr)
{
    int mij,sol;

    for (sol=-1; st<=dr; )
    {
        mij=(st+dr)>>1;

        if (sum[x][mij]>=val)
        {
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }

    if (sol==-1 || sum[x][sol]!=val)
        return -1;

    return sol;
}

inline int caut_bin_y (long long val,int y,int st,int dr)
{
    int mij,sol;

    for (sol=-1; st<=dr; )
    {
        mij=(st+dr)>>1;

        if (sum[mij][y]>=val)
        {
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }

    if (sol==-1 || sum[sol][y]!=val)
        return -1;

    return sol;
}

inline int valid (int x1,int y1,int x2,int y2)
{
    int a[LIM];
    int i;

    a[1]=sum[x1][y1];
    a[2]=sum[x1][y2]-sum[x1][y1];
    a[3]=sum[x1][N]-sum[x1][y2];
    a[4]=sum[x2][y1]-sum[x1][y1];
    a[5]=sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];
    a[6]=sum[x2][N]-sum[x1][N]-sum[x2][y2]+sum[x1][y2];
    a[7]=sum[N][y1]-sum[x2][y1];
    a[8]=sum[N][y2]-sum[N][y1]-sum[x2][y2]+sum[x2][y1];
    a[9]=sum[N][N]-sum[N][y2]-sum[x2][N]+sum[x2][y2];

    sort (a+1,a+LIM);
    for (i=1; i<LIM; ++i)
        if (a[i]!=v[i])
            return 0;

    return 1;
}

void solve ()
{
    int i,j,k,x1,x2,y1,y2;

    for (i=1; i<LIM; ++i)
        for (x1=0; x1<N; ++x1)
        {
            x2=caut_bin_x (v[i],x1,0,N-1);

            if (x2!=-1)
                for (j=1; j<LIM; ++j)
                    if (i!=j)
                    {
                        y1=caut_bin_y (v[i]+v[j],x2,x1+1,N-1);

                        if (y1!=-1)
                            for (k=1; k<LIM; ++k)
                                if (i!=k && j!=k)
                                {
                                    y2=caut_bin_x (v[i]+v[k],x1,x2+1,N-1);

                                    if (y2!=-1)
                                        if (valid (x1,x2,y1,y2))
                                        {
                                            printf ("%d %d %d %d",x1,y1,x2,y2);

                                            return ;
                                        }
                                }
                    }
        }
}

int main ()
{
    freopen ("zone.in","r",stdin);
    freopen ("zone.out","w",stdout);

    read ();
    solve ();

    return 0;
}