Cod sursa(job #3322669)

Utilizator Mike_RossMIke Ross Mike_Ross Data 15 noiembrie 2025 10:41:24
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.69 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zone.in");
ofstream cout ("zone.out");

int n;
int sume[10];
int a[515][515];
int sump[515][515];
int s[515*515];
int p1x,p1y,p2x,p2y;
bool amsolutie=0;
int lr1,lr2,cr1,cr2;

int cbin(int x, int st, int dr)
{
    while (st<=dr)
    {
        //cout<<"st: "<<st<<' '<<"dr: "<<dr<<endl;
        int mij=(st+dr)/2;
        if (x>sume[mij])
            st=mij+1;
        else
            dr=mij-1;
    }

    if (sume[st]==x)
        return 1;
    else
        return 0;
}

int verif(int &l1, int &l2, int &c1, int &c2)
{
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
        {
            p1x=i;
            p1y=j;
            int saux=sump[p1x][p1y];
            //cout<<i<<' '<<j<<' '<<saux<<endl;
            //cout<<"saux: "<<saux<<endl;
            if (cbin(saux,1,9)==1)
            {
                //cout<<i<<' '<<j<<' '<<saux<<' '<<cbin(saux,1,9)<<endl;

                for (int p=i+1; p<=n; p++)
                {
                    bool gasit=1;

                    for (int q=j+1; q<=n && gasit==1; q++)
                    {
                        p2x=p;
                        p2y=q;
                        //cout<<p<<' '<<q<<endl;
                        //cout<<i<<' '<<j<<' '<<p<<' '<<q<<endl;
                        //cout<<"saux: "<<saux<<endl;
                        s[1]=sump[i][j];
                        s[2]=sump[i][q]-sump[i][j];
                        s[3]=sump[i][n]-sump[i][q];
                        s[4]=sump[p][j]-sump[i][j];
                        s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
                        s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
                        s[7]=sump[n][j]-sump[p][j];
                        s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
                        s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
                        sort(s+1,s+1+9);
                        for (int f=1; f<=9; f++)
                            if (s[f]!=sume[f])
                            {
                                gasit=0;
                                break;/*cout<<s[f]<<' '<<sume[f]<<' '<<gasit<<endl;*/
                            }
                        if (gasit==1)
                            //cout<<i<<' '<<p<<' '<<j<<' '<<q<<endl;
                        if (amsolutie==0){
                        l1=n;
                        l2=p;
                        c1=j;
                        c2=q;
                        lr1=i;
                        lr2=p;
                        cr1=j;
                        cr2=q;
                        amsolutie=1;}

                    }
                }
            }
        }
}

int main()
{
    cin>>n;
    for (int i=1; i<=9; i++)
        cin>>sume[i];
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
        {
            cin>>a[i][j];
            sump[i][j]=a[i][j]+sump[i-1][j]+sump[i][j-1]-sump[i-1][j-1];
        }
    sort(sume+1,sume+1+9);
    /*for (int i=1; i<=9; i++)
        cout<<sume[i]<<' ';
    cout<<endl;*/
    /*for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
    {
        p1x=i;
        p1y=j;
        int saux=sump[p1x][p1y];
        if (cbin(s,1,9)==1)
        {
            for (int p=i+1;p<=n;p++)
                for (int q=j+1;j<=n;q++)
            {
                p2x=p;
                p2y=q;
                s[1]=saux;
                s[2]=sump[i][q]-sump[i][j];
                s[3]=sump[i][n]-sump[i][q];
                s[4]=sump[p][j]-sump[i][j];
                s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
                s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
                s[7]=sump[n][i]-sump[p][j];
                s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
                s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
                sort(s+1,s+1+9);
                for (int f=1;f<=9;f++)
                    if (s[f]!=sume[f])

            }
        }
    }*/
    int a=0,b=0,c=0,d=0;
    verif(a,b,c,d);
    //cout<<a<<' '<<b<<' '<<c<<' '<<d;
    cout<<lr1<<' '<<lr2<<' '<<cr1<<' '<<cr2;
    /*int i=1;
    int p=3;
    int j=2;
    int q=3;
    s[1]=sump[i][j];
    s[2]=sump[i][q]-sump[i][j];
    s[3]=sump[i][n]-sump[i][q];
    s[4]=sump[p][j]-sump[i][j];
    s[5]=sump[p][q]-sump[i][q]-sump[p][j]+sump[i][j];
    s[6]=sump[p][n]-sump[i][n]-sump[p][q]+sump[i][q];
    s[7]=sump[n][j]-sump[p][j];
    s[8]=sump[n][q]-sump[p][q]-sump[n][j]+sump[p][j];
    s[9]=sump[n][n]-sump[p][n]-sump[n][q]+sump[p][q];
    sort(s+1,s+1+9);
    for (int i=1; i<=9; i++)
        cout<<s[i]<<' ';*/
    return 0;
}