Cod sursa(job #1523272)

Utilizator radu_uniculeu sunt radu radu_unicul Data 12 noiembrie 2015 15:45:11
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
#include<stdio.h>
#include<algorithm>
#define ll long long
using namespace std;
ll n,b[10],m[520][520],sp[520][520],c1,c2,l1,l2,c1l1,sume[10],v1,v2,v4;
ll val(ll a,ll b,ll x,ll y)
{
    return sp[x][y]+sp[a-1][b-1]-sp[x][b-1]-sp[a-1][y];
}
bool check(ll a)
{
    for(int i=1; i<=9; i++) if(a==b[i]&&!sume[i]) return 1;
    return 0;
}
ll cautbincol(ll a,ll b,ll x,ll v)
{
    ll pas=1<<10,start=0;
    for(pas; pas>0; pas=pas>>1)
    {
        if(start+pas>n) continue;
        if(val(a,b,x,start+pas)<v) start=start+pas;
        else if(val(a,b,x,start+pas)==v)
        {
            return start+pas;
        }
    }
    return 0;
}
ll cautbinlin(ll a,ll b,ll y,ll v)
{
    ll pas=1<<10,start=0;
    for(pas; pas>0; pas=pas>>1)
    {
        if(start+pas>n) continue;
        if(val(a,b,start+pas,y)<v) start=start+pas;
        else if(val(a,b,start+pas,y)==v)
        {
            return start+pas;
        }
    }
    return 0;
}
int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1; i<=9; ++i) scanf("%lld",&b[i]);
    sort(b+1,b+10);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j) scanf("%lld",&m[i][j]);
    sp[1][1]=m[1][1];
    for(ll j=2; j<=n; ++j) sp[j][1]=sp[j-1][1]+m[j][1];
    for(ll i=2; i<=n; ++i) sp[1][i]=sp[1][i-1]+m[1][i];
    for(ll i=1; i<=n; i++)
        for(ll j=2; j<=n; j++) sp[i][j]=sp[i-1][j]+sp[i][j-1]+m[i][j]-sp[i-1][j-1];
    for(ll i=1; i<=n; i++)
    {
        l1=i;
        for(v1=1; v1<=9; v1++)
        {
            if(cautbincol(1,1,l1,b[v1]))
            {
                c1=cautbincol(1,1,l1,b[v1]);
                for(v2=1; v2<=9; v2++)
                {
                    if(v1!=v2)
                    {
                        if(cautbinlin(l1+1,1,c1,b[v2])&&cautbinlin(l1+1,1,c1,b[v2])>l1)
                        {
                            l2=cautbinlin(l1+1,1,c1,b[v2]);
                            for(v4=1; v4<=9; v4++)
                                if(v4!=v1&&v4!=v2)
                                {
                                    if(cautbincol(1,c1+1,l1,b[v4])&&cautbincol(1,c1+1,l1,b[v4])>c1)
                                    {
                                        c2=cautbincol(1,c1+1,l1,b[v4]);
                                        sume[1]=val(1,1,l1,c1);
                                        sume[2]=val(1,c1+1,l1,c2);
                                        sume[3]=val(1,c2+1,l1,n);
                                        sume[4]=val(l1+1,1,l2,c1);
                                        sume[5]=val(l1+1,c1+1,l2,c2);
                                        sume[6]=val(l1+1,c2+1,l2,n);
                                        sume[7]=val(l2+1,1,n,c1);
                                        sume[8]=val(l2+1,c1+1,n,c2);
                                        sume[9]=val(l2+1,c2+1,n,n);
                                        sort(sume+1,sume+10);
                                        bool flag=0;
                                        for(int sol=1; sol<=9; sol++)
                                        {
                                            if(sume[sol]!=b[sol]) flag=1;
                                        }
                                        if(!flag)
                                        {
                                            printf("%lld %lld %lld %lld",l1,l2,c1,c2);
                                            return 0;
                                        }
                                    }
                                }
                        }
                    }
                }
            }
        }
    }
}