Cod sursa(job #2358007)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 27 februarie 2019 20:50:28
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.55 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("zone.in");
ofstream g("zone.out");
long long a[513][513],b[513][513],v[11];
int l1,c1,l2,c2,i,j,k1,k2,k3,k4,ok,viz[10],n,m,fr[11];
int cautbin(long long S){
    int st=1,dr=m,mid;
    while(st<=dr){
        mid=(st+dr)/2;
        if(v[mid]<S)
            st=mid+1;
        else if(v[mid]>S)
            dr=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;
}
void resetViz(int poz){
    for(int h=1;h<=m;h++)
        viz[h]=fr[h];
    if(poz>=1)
        viz[k1]--;
    if(poz>=2)
        viz[k2]--;
    if(poz>=3)
        viz[k3]--;
}
int valid(){
    for(int h=1;h<=m;h++)
        viz[h]=0;
    viz[k4]=viz[k3]=viz[k2]=viz[k1]=1;
    int k5=cautbin(b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1]);
    int k6=cautbin(b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][c2]);
    int k7=cautbin(b[n][c1]-b[l2][c1]);
    int k8=cautbin(b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1]);
    int 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[k8]++;
    viz[k9]++;
    for(int h=1;h<=m;h++)
        if(viz[h]>fr[h])
            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];
    sort(v+1,v+10);
    m=0;
    int nr=1;
    for(i=1;i<=8;i++)
        if(v[i]!=v[i+1]){
            fr[++m]=nr;
            v[m]=v[i];
            nr=1;
        }
        else
            nr++;
    if(v[i]!=v[i+1]){
        fr[++m]=nr;
        v[m]=v[i];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            f>>a[i][j];
            b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    for(l1=1;l1<=n-2;l1++){
        for(k1=1;k1<=m;k1++){
            resetViz(0);
            c1=cautc(v[k1],l1,1,n-2);
            if(c1!=-1){
                viz[k1]--;
                for(k2=1;k2<=m;k2++){
                    resetViz(1);
                    c2=cautc(v[k1]+v[k2],l1,c1+1,n-1);
                    if(c2!=-1&&viz[k2]>=1){
                        viz[k2]--;
                        ok=0;
                        for(k3=1;k3<=m;k3++){
                            if(b[l1][n]==v[k1]+v[k2]+v[k3]&&viz[k3]>=1){
                                ok=1;
                                break;
                            }
                        }
                        viz[k3]--;
                    }
                    if(ok==1){
                        for(k4=1;k4<=m;k4++){
                            resetViz(3);
                            l2=cautl(v[k1]+v[k4],c1,l1+1,n-1);
                            if(l2!=-1&&viz[k4]>=1){
                                if(valid()==1){
                                    g<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}