Cod sursa(job #2357482)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 27 februarie 2019 14:23:45
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <fstream>

using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
long long a[512][512];
int cautbin(long long S){
    int st=1,dr=n;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid]<S)
            st=mid+1;
        else if(v[mid]>S)
            st=mid-1;
        else
            return mid;
    }
    return -1;
}
int cautc(long long S,int x,int st,int dr){
    int mid;
    while(st<=dr){
        mid=(st+dr)/2;
        if(b[x][mid]==S)
            return mid;
        else if(b[x][mid]>S)
            dr=mid-1;
        else
            st=mid+1;
    }
    return -1;
}
int valid(){
    viz[k4]=viz[k3]=viz[k2]=viz[k1]=1;
        k5=cautbin(b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1]);
        k6=cautbin(b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][c2]);
        k7=cautbin(b[n][c1]-b[l2][c1]);
        k8=cautbin(b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1]);
        k9=cautbin(b[n][n]-b[l2][n]-b[n][c2]+b[l2][c2]);
        if(k5==-1||k6==-1||k7==-1||k8==-1||k9==-1)
            return 0;
        viz[k5]++;
        viz[k6]++;
        viz[k7]++;
        viz[k7]++;
        viz[k8]++;
        viz[k9]++;
        for(int i=1;i<=9;i++)
            if(viz[i]>=2)
                return 0;
    return 1;
}
int cautl(long long S,int y,int st,int dr){
    int mid;
    while(st<=dr){
        mid=(st+dr)/2;
        if(b[mid][y]==S)
            return mid;
        else if(b[mid][y]>S)
            dr=mid-1;
        else
            st=mid+1;
    }
    return -1;
}
int main ()
{   f>>n;
    for(i=1;i<=9;i++)
        f>>v[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            f>>a[i][j];
            b[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    sort(v+1,v+10);
    for(l1=2;l1<=n-2;l1++){
        for(k1=1;k1<=9;k1++){
            c1=cautc(v[k1],l1,1,n-2);
            if(c1!=-1)
            for(k2=1;k2<=9;k2++){
                if(k2!=k1){
                    c2=cautc(v[k1]+v[k2],l1,c1+1,n-1);
                    if(c2!=-1){
                        for(k3=1;k3<=9;k3++){
                            ok=0;
                            if(k3!=k2&&k3!=k1)
                                if(b[l1][n]==v[k1]+v[k2]+v[k3])
                                    ok=1;
                        }
                    }
                    if(ok==1){
                        for(k4=1;k4<=9;k4++){
                            if(k4!=k3&&k4!=k2&&k4!=k1){
                                l2=cautl(v[k1]+v[k4],c1,l1+1,n-1);
                                if(l2!=-1){
                                    if(valid()==1){
                                        g<<l1<<' '<<c1<<' '<<l2<<' '<<c2;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}