Cod sursa(job #2072060)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 21 noiembrie 2017 12:51:33
Problema Zone Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.16 kb
#include <fstream>

using namespace std;
ifstream fin ("zone.in");
ofstream fout("zone.out");
long long v[514][514],s[11];
long long f[11], i, j, n,c1,c2,l1,l2,k1,k2,k3,st,dr,mid;

int verificare()
{
    int i;
    int ok=1;
    for(i=1;i<=9;i++)
        if(0LL+v[l1][n]-v[l1][c2]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
        if(0LL+v[n][c1]-v[l2][c1]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
        if(0LL+v[l2][c2]-v[l2][c1]-v[l1][c2]+v[l1][c1]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
        if(0LL+v[l2][n]-v[l2][c2]-v[l1][n]+v[l1][c2]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
        if(0LL+v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
        if(0LL+v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]==s[i]&&f[i]==0)
            f[i]=1;
    for(i=1;i<=9;i++)
    {
        if(f[i]==0)
            ok=0;
        f[i]=0;
    }
    return ok;
}

int main ()
{
    fin>>n;
    for(i=1;i<=9;i++)
        fin>>s[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fin>>v[i][j];
            v[i][j]+=v[i][j-1]+v[i-1][j]-v[i-1][j-1];
        }
    for(k1=1;k1<=9;k1++)
        for(k2=1;k2<=9;k2++)
            if(k2!=k1)
                for(k3=1;k3<=9;k3++)
                    if(k3!=k2&&k3!=k1)
                        for(l1=1;l1<n-1;l1++)
                        {
                            l2=-1;c1=-1;c2=-1;
                            st=1;
                            dr=n-2;
                            while(st<=dr)
                            {
                                mid=(st+dr)/2;
                                if(v[l1][mid]<=s[k1])
                                {
                                    if(c1==-1)
                                        c1=mid;
                                    else
                                        c1=min(c1, mid);
                                    st=mid+1;
                                }
                                else
                                    dr=mid-1;
                            }
                            if(v[l1][c1]!=s[k1])
                                continue;
                            st=l1+1;
                            dr=n-1;
                            while(st<=dr)
                            {
                                mid=(st+dr)/2;
                                if(v[mid][c1]-v[l1][c1]<=s[k3])
                                {
                                    if(l2==-1)
                                        l2=mid;
                                    else
                                        l2=min(l2, mid);
                                    st=mid+1;
                                }
                                else
                                    dr=mid-1;
                            }
                            if(v[l2][c1]-v[l1][c1]!=s[k3])
                                continue;
                            st=c1+1;
                            dr=n-1;
                            while(st<=dr)
                            {
                                mid=(st+dr)/2;
                                if(v[l1][mid]-v[l1][c1]<=s[k2])
                                {
                                    if(c2==-1)
                                        c2=mid;
                                    else
                                        c2=min(c2, mid);
                                    st=mid+1;
                                }
                                else
                                    dr=mid-1;
                            }
                            if(v[l1][c2]-v[l1][c1]!=s[k2])
                                continue;
                            f[k1]=1;
                            f[k2]=1;
                            f[k3]=1;
                            if(verificare()==1)
                            {
                                fout<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
                                return 0;
                            }
                        }
    return 0;
}