Cod sursa(job #2197761)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 22 aprilie 2018 20:43:01
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("zone.in");
ofstream out ("zone.out");
long long v[520][520],s[520][520],val[11],vv[11],n;
long long col (long long poz, long long i, long long j)
{
    long long pas=1<<10,k=poz;
    while(pas)
    {
        if(k+pas<=n && s[i][k+pas]-s[i][poz-1]<=val[j])
            k+=pas;
        pas>>=1;
    }
    if(s[i][k]-s[i][poz-1]==val[j])
        return k;
    return -1;
}
long long lin (long long poz, long long i, long long j)
{
    long long pas=1<<10,k=poz;
    while(pas)
    {
        if(k+pas<=n && s[k+pas][i]-s[poz-1][i]<=val[j])
            k+=pas;
        pas>>=1;
    }
    if(s[k][i]-s[poz-1][i]==val[j])
        return k;
    return -1;
}
bool verif (long long l1, long long l2, long long c1, long long c2)
{
    vv[1]=s[l1][c1];
    vv[2]=s[l1][c2]-vv[1];
    vv[3]=s[l1][n]-s[l1][c2];
    vv[4]=s[l2][c1]-vv[1];
    vv[5]=s[l2][c2]-s[l1][c2]-s[l2][c1]+vv[1];
    vv[6]=s[l2][n]-s[l2][c2]-vv[3];
    vv[7]=s[n][c1]-s[l2][c1];
    vv[8]=s[n][c2]-s[l2][c2]-vv[7];
    vv[9]=s[n][n]-s[l2][n]-s[n][c2]+s[l2][c2];
    sort(vv+1,vv+10);
    for(long long i=1;i<=9;i++)
        if(vv[i]!=val[i])
            return false;
    return true;
}
int main()
{
    long long i,j,a,b,c,jj,jjj;
    in>>n;
    for(i=1;i<=9;i++)
        in>>val[i];
    sort(val+1,val+10);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            in>>v[i][j];
            s[i][j]=v[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=9;j++)
        {
            a=col(1,i,j);
            if(a==-1)
                continue;
            for(jj=1;jj<=9;jj++)
            {
                if(jj!=j)
                {
                    b=col(a+1,i,jj);
                    if(b==-1)
                        continue;
                    for(jjj=1;jjj<=9;jjj++)
                    {
                        if(jjj!=jj && jjj!=j)
                        {
                            c=lin(i+1,a,jjj);
                            if(c==-1)
                                continue;
                            if(verif(i,c,a,b))
                            {
                                out<<i<<' '<<c<<' '<<a<<' '<<b;
                                i=n+1;
                                j=jj=jjj=1000;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}