Cod sursa(job #2474810)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 15 octombrie 2019 20:47:10
Problema Zone Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
int n,a[10],sum[513][513],x,i,j,c1,c2,l1,l2,b[10];
int suma(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
bool cauta_binar(int val)
{
    int st,dr,mij;
    st=1;
    dr=9;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a[mij]==val)
        {
            return 1;
        }
        else
        {
            if(a[mij]<val)
            {
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
    }
    return 0;
}
bool verifica()
{
    int i;
    b[1]=suma(1,1,l1,c1);
    b[2]=suma(1,c1+1,l1,c2);
    b[3]=suma(1,c2+1,l1,n);
    b[4]=suma(l1+1,1,l2,c1);
    b[5]=suma(l1+1,c1+1,l2,c2);
    b[6]=suma(l1+1,c2+1,l2,n);
    b[7]=suma(l2+1,1,n,c1);
    b[8]=suma(l2+1,c1+1,n,c2);
    b[9]=suma(l2+1,c2+1,n,n);
    sort(b+1,b+10);
    for(i=1;i<=9;i++)
    {
        if(b[i]!=a[i])
            return 0;
    }
    return 1;
}
int main()
{
    f>>n;
    for(i=1;i<=9;i++)
    {
        f>>a[i];
    }
    sort(a+1,a+10);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            f>>x;
            sum[i][j]=x+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    }
    for(l1=1;l1<=n-2;l1++)
    {
        for(c1=1;c1<=n-2;c1++)
        {
            if(cauta_binar(suma(1,1,l1,c1))==1)
            {
                for(l2=l1+1;l2<=n-1;l2++)
                {
                    if(cauta_binar(suma(l1+1,1,l2,c1))==1)
                    {
                        for(c2=c1+1;c2<=n-1;c2++)
                        {
                            if(verifica()==1)
                            {
                                g<<l1<<" "<<l2<<" "<<c1<<" "<<c2<<"\n";
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}