Cod sursa(job #1758900)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 18 septembrie 2016 00:55:37
Problema Zone Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include<bits/stdc++.h>
#define dim 1000005
using namespace std;
int n,val[15],seen[15],a[1005][1005],l1,l2,s[1005][1005],s1,s2,s3,x;
char buff[dim+5];
int poz=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;
}
int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
   // scanf("%d",&n);
   fread(buff,1,dim,stdin);
   citeste(n);
    for(int i=1;i<=9;i++)
    {
        //scanf("%d",&val[i]);
        citeste(val[i]);
    }
    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 c1=1;c1<=n;c1++)
    {
        for(int c2=(c1+1);c2<=n;c2++)
        {
            l1=0;
            l2=0;
            for(int l=1;l<=n;l++)
            {
                s1=s[l][c1];
                s2=s[l][c2]-s[l][c1];
                s3=s[l][n]-s1-s2;
                for(int i=1;i<=9;i++) seen[i]=0;
                if (cautare(s1))
                {
                    x=cautare(s1);
                    seen[x]=1;
                    if (cautare(s2))
                    {
                        x=cautare(s2);
                        seen[x]=1;
                        if (cautare(s3))
                        {
                            l1=l;
                            break;
                        }
                    }
                }
            }

            /////////
            if (l1)
            {
            for(int l=n-1;l>=1;l--)
            {
                s1=s[n][c1];
                s2=s[n][c2]-s[n][c1];
                s3=s[n][n]-s[n][c2];
                s1=s1-s[l][c1];
                s2=s2-s[l][c2]+s[l][c1];
                s3=s3-s[l][n]+s[l][c2];
                for(int i=1;i<=9;i++) seen[i]=0;
                if (cautare(s1))
                {
                    x=cautare(s1);
                    seen[x]=1;
                    if (cautare(s2))
                    {
                        x=cautare(s2);
                        seen[x]=1;
                        if (cautare(s3))
                        {
                            l2=l;
                            break;
                        }
                    }
                }
            }
            if (l1 && l2)
            {
                printf("%d %d %d %d\n",l1,l2,c1,c2);
                break;
            }
            }
            ////////
        }
    }
}