Cod sursa(job #1164810)

Utilizator thewildnathNathan Wildenberg thewildnath Data 2 aprilie 2014 12:22:08
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define NMAX 520
#define fs first
#define sc second


int n;
long long s[NMAX][NMAX];
long long val[10],perm[10];

pair<pair<int,int>,pair<int,int> > sol,aux;

inline long long suma(int p1,int p2)
{
    int i;
    long long sum=0;

    for(i=p1;i<=p2;++i)
        sum+=val[perm[i]];
    return sum;
}

inline long long suma_mat(int x1,int y1,int x2,int y2)
{
    return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}

int caut_lin(int col,int st,int dr,long long sum)
{
    int med;

    while(st<=dr)
    {
        med=(st+dr)>>1;

        if(s[med][col]==sum)
            return med;

        if(s[med][col]<sum)
            st=med+1;
        else
            dr=med-1;
    }
    return 0;
}
int caut_col(int lin,int st,int dr,long long sum)
{
    int med;

    while(st<=dr)
    {
        med=(st+dr)>>1;

        if(s[lin][med]==sum)
            return med;

        if(s[lin][med]<sum)
            st=med+1;
        else
            dr=med-1;
    }
    return 0;
}

int gaseste(int &lin1,int &lin2,int &col1,int &col2)
{
    long long sum;

    sum=suma(1,3);
    lin1=caut_lin(n,1,n,sum);
    if(!lin1)return 0;

    sum=suma(1,6);
    lin2=caut_lin(n,lin1+1,n,sum);
    if(!lin2)return 0;

    sum=suma(1,1);
    col1=caut_col(lin1,1,n,sum);
    if(!col1)return 0;

    sum=suma(1,2);
    col2=caut_col(lin1,col1+1,n,sum);
    if(!col2)return 0;

    return 1;
}

int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    int i,j,x,lin1,lin2,col1,col2;

    scanf("%d",&n);
    for(i=1;i<=9;++i)
        scanf("%lld",&val[i]),perm[i]=i;

    for(i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j)
        {
            scanf("%d",&x);

            s[i][j]=(long long)x+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }

    sol=make_pair(make_pair(n,n),make_pair(n,n));

    do
    {
        if(!gaseste(lin1,lin2,col1,col2))
            continue;

        if(suma_mat(lin1+1,1,lin2,col1) != suma(4,4))
            continue;
        if(suma_mat(lin1+1,col1+1,lin2,col2) != suma(5,5))
            continue;
        if(suma_mat(lin1+1,col2+1,lin2,n) != suma(6,6))
            continue;
        if(suma_mat(lin2+1,1,n,col1) != suma(7,7))
            continue;
        if(suma_mat(lin2+1,col1+1,n,col2) != suma(8,8))
            continue;
        if(suma_mat(lin2+1,col2+1,n,n) != suma(9,9))
            continue;

        aux=make_pair(make_pair(lin1,lin2),make_pair(col1,col2));

        if(aux<sol)
            sol=aux;
    }while(next_permutation(perm+1,perm+10));

    printf("%d %d %d %d\n",sol.fs.fs,sol.fs.sc,sol.sc.fs,sol.sc.sc);

    return 0;
}