Cod sursa(job #1759414)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 19 septembrie 2016 09:04:39
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.35 kb
#include<bits/stdc++.h>
#define dim 1000005
#define INF INT_MAX
using namespace std;
int n,seen[15],v[15],a[1005][1005],l1,l2,s[1005][1005],s1,s2,s3,x,c2;
char buff[dim+5];
int poz=0,l1x,l2x,c1x,c2x,c1,st,dr,mid,j2,y;
vector<int> el,el1;
bool find(int x)
{
    for(int i=0;i<el.size();i++)
        if (el[i]==x) return 1;
    return 0;
}
bool cautare(int x)
{
    for(int i=1;i<=9;i++)
    {
        if(v[i]==x && !find(i)) return 1;
    }
    return 0;
}
void citeste(int &numar)
{
    numar=0;
    while (buff[poz]<'0' || buff[poz]>'9')
    {
        poz++;
        if (poz==dim)
        {
            poz=0;
            fread(buff,1,dim,stdin);
        }
    }
    while (buff[poz]>='0' && buff[poz]<='9')
    {
        numar=numar*10+buff[poz]-'0';
        poz++;
        if (poz==dim)
        {
            poz=0;
            fread(buff,1,dim,stdin);
        }
    }
}
/*int cautare(int x)
{
    int st,dr,mid;
    st=1;
    dr=9;
    while( st<=dr)
    {
        mid=(st+dr)>>1;
        if (val[mid]==x)
        {
            if (!seen[mid]) return mid;
                else
            {
                int i=mid-1;
                while (!(i>=1 && val[i]==x && !seen[i])) i--;
                if (val[i]==x) return i;
                i=mid+1;
                while (!(i<=n && val[i]==x && !seen[i])) i++;
                if (val[i]==x) return i;
            }
        }
            else
        if (val[mid]<x) st=mid+1;
            else dr=mid-1;
    }
    return 0;
}*/
bool sol=0,ok5,ok7;
int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
   // scanf("%d",&n);
   fread(buff,1,dim,stdin);
   citeste(n);
  // val.push_back(-1);
    for(int i=1;i<=9;i++)
    {
        //scanf("%d",&val[i]);
        citeste(v[i]);
      //  val.push_back(x);
    }
  //  sort(val+1,val+10);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //scanf("%d",&a[i][j]);
            citeste(a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        s[1][i]=s[1][i-1]+a[1][i];
        s[i][1]=s[i-1][1]+a[i][1];
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=9 && !sol;i++)
    {
        el.clear();
        el.push_back(i);
        l1x=c1x=l2x=c2x=0;
        for(int l1=1;l1<=(n-2);l1++)
        {
             c1=0;
            st=1;
            dr=n-2;
            while(st<=dr)
            {
                mid=(st+dr)>>1;
                if (s[l1][mid]==v[i])
                {
                    c1=mid;
                    st=dr+1;
                }
                    else
                if (s[l1][mid]<v[i]) st=mid+1;
                    else dr=mid-1;
            }
            if (c1)
            {
                l1x=l1;
                c1x=c1;
                break;
            }
        }
        if (l1x && c1x)
        {
            c2x=INF;
        for(int j=1;j<=9;j++)
        {
            if (j!=i)
            {
                st=c1+1;
                dr=n-1;
                c2=0;
                while(st<=dr)
                {
                    mid=(st+dr)>>1;
                    if (s[l1x][mid]==(v[i]+v[j]))
                    {
                        c2=j;
                        st=dr+1;
                    }
                        else
                    if (s[l1x][mid]<(v[i]+v[j])) st=mid+1;
                        else dr=mid-1;
                }
                if (c2 && c2<c2x) c2x=c2,j2=j;
            }

        }
            if (c2x<INF)
            {
                el.push_back(j2);
                y=s[l1x][n]-s[l1x][c2x];
                bool ok=0;
                for(int j=1;j<=9;j++)
                {
                    if (v[j]==y && !find(j))
                    {
                        ok=1;
                    }
                }
                if (!ok) c2x=0;
            }
            if (c2x)
            {
                l2x=INF;
                for(int j=1;j<=9;j++)
                {
                    if (!find(j))
                    {
                    st=l1+1;
                    dr=n-1;
                    l2=0;
                        while (st<=dr)
                        {
                            mid=(st+dr)>>1;
                            if ((s[mid][c1x]-s[l1x][c1x])==v[j])
                            {
                                l2=mid;
                                st=dr+1;
                            }
                                else
                            if ((s[mid][c1x]-s[l1x][c1x])<v[j])
                            {
                                st=mid+1;
                            }
                                else dr=mid-1;
                        }
                    if (l2 && l2<l2x)
                    {
                        //l2x=l2;
                       // j2=j;
                       el1.clear();
                       for(int j=0;j<el.size();j++) el1.push_back(el[j]);
                        el.push_back(j2);
                        int s5=s[l2][c2x]-s[l2][c1x]-s[l1x][c2x]+s[l1x][c1x];
                        int s6=s[l2][c2x]-s[l1x][c2x]-s[l2][c1x]+s[l1x][c1x];
                        int s7=s[n][c1x]-s[l2][c1x];
                        int s8=s[n][c2x]-s[l2][c2x]-s[n][c1x]+s[l2][c1x];
                        int s9=s[n][n]-s[n][c2x]-s[l2][n]+s[l2][c2x];
                        if (cautare(s5) && cautare(s6) && cautare(s7) && cautare(s8) && cautare(s9))
                        {
                            l2x=l2;
                            j2=j;
                        }
                            else
                        {
                            el.clear();
                            for(int j=0;j<el1.size();j++)
                            {
                                el.push_back(el1[j]);
                            }
                        }

                    }
                    }
                }
                if (l2x<INF)
                {
                    {
                        printf("%d %d %d %d\n",l1x,l2x,c1x,c2x);
                        sol=1;
                    }
                //
                }
            }
        }
    }
}