Cod sursa(job #2358331)

Utilizator mihaimodiMihai Modi mihaimodi Data 28 februarie 2019 00:01:11
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.66 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
long long a[515][515],v[10],s[10];
bool viz[10];
int x,n;
int cautbin_lin2(long long val, int l1, int c1)
{
    int st=l1,dr=n-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        long long nr=a[mid][c1]-a[l1][c1];
        if(nr==val)
            return mid;
        else if(nr>val)
            dr=mid-1;
        else
            st=mid+1;
    }
    return -1;
}
int cautbin_col(int l, int st, int dr, long long val, int colst)
{
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(val==a[l][mid]-a[l][colst])
            return mid;
        else if(a[l][mid]-a[l][colst]>val)
            dr=mid-1;
        else if(a[l][mid]-a[l][colst]<val)
            st=mid+1;
    }
    return -1;
}
bool verif(int l1, int l2, int c1, int c2)
{
    long long aux[10];
    for(int i=1;i<=4;i++)
        aux[i]=v[i];
    aux[5]=a[l2][c2]+a[l1][c1]-a[l1][c2]-a[l2][c1];
    aux[6]=a[l2][n]+a[l1][c2]-a[l1][n]-a[l2][c2];
    aux[7]=a[n][c1]-a[l2][c1];
    aux[8]=a[n][c2]+a[l2][c1]-a[l2][c2]-a[n][c1];
    aux[9]=a[n][n]+a[l2][c2]-a[l2][n]-a[n][c2];
    sort(aux+1,aux+10);
    for(int i=1;i<=9;i++)
        if(aux[i]!=s[i])
            return 0;
    return 1;
}
int main()
{
    fin>>n;
    for(int i=1;i<=9;i++)
        fin>>s[i];
    sort(s+1,s+10);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            fin>>x;
            a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }

    for(int l1=1;l1<=n-2;l1++)
        for(int s1=1;s1<=9;s1++)
            if(!viz[s1])
            {
                int c1=cautbin_col(l1,1,n-2,s[s1],1);
                if(c1!=-1)
                {
                    viz[s1]=1;
                    v[1]=a[l1][c1];
                    for(int s2=1;s2<=9;s2++)
                        if(!viz[s2])
                        {
                            viz[s2]=1;
                            int c2=cautbin_col(l1,c1+1,n-1,s[s2],c1);
                            if(c2!=-1)
                            {
                                viz[s2]=1;
                                v[2]=a[l1][c2]-a[l1][c1];
                                int sum3=a[l1][n]-a[l1][c2];
                                for(int s3=1;s3<=9;s3++)
                                    if(!viz[s3]&&s[s3]==sum3)
                                    {
                                        viz[s3]=1;
                                        v[3]=sum3;
                                        for(int s4=1;s4<=9;s4++)
                                            if(!viz[s4])
                                            {
                                                int l2=cautbin_lin2(s[s4],l1,c1);
                                                if(l2!=-1)
                                                {
                                                    v[4]=s[s4];
                                                    if(verif(l1,l2,c1,c2))
                                                    {
                                                        fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
                                                        return 0;
                                                    }
                                                }
                                            }
                                        viz[s3]=0;
                                    }
                            }
                            viz[s2]=0;
                        }
                    }
                    viz[s1]=0;
                }
    return 0;
}