Cod sursa(job #1937705)

Utilizator tgm000Tudor Mocioi tgm000 Data 24 martie 2017 10:09:41
Problema Zone Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int a[513][513];
long long v[10];
long long r[10];
long long suma(int l1,int c1,int l2,int c2){
    return 1LL*a[l2][c2]-a[l1-1][c2]-a[l2][c1-1]+a[l1-1][c1-1];
}
int exista(int nr){
    int st=1,dr=9,m,poz=0;
    while(st<=dr){
        m=(st+dr)/2;
        if(v[m]>=nr){
            dr=m-1;
            poz=m;
        }else
            st=m+1;
    }
    if(v[poz]==nr)
        return 1;
    return 0;
}
int main(){
    int n,i,j,ind,l1,c1,st,dr,m,s,l2,c2,k;
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=9;i++)
        scanf("%lld",&v[i]);
    sort(v+1,v+10);
    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++){
        scanf("%d",&a[i][j]);
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
     }
    ind=1;
    for(l1=1;l1<=n-2;l1++)
        for(c1=1;c1<=n-2;c1++){
          while(v[ind]<a[l1][c1])
                ind++;
          if(v[ind]==a[l1][c1]){
            for(i=1;i<=9;i++){
                if(i!=ind){
                    st=l1+1;
                    dr=n;
                    while(st<=dr){
                        m=(st+dr)/2;
                        s=suma(l1+1,1,m,c1);
                        if(s>=v[i]){
                            dr=m-1;
                            l2=m;
                        }else
                            st=m+1;
                    }
                    if(suma(l1+1,1,l2,c1)==v[i]&&exista(suma(l2+1,1,n,c1))){
                        for(j=1;j<=9;j++)
                            if(j!=i&&j!=ind){
                                st=c1+1;
                                dr=n;
                                while(st<=dr){
                                    m=(st+dr)/2;
                                    s=suma(1,c1+1,l1,m);
                                    if(s>=v[j]){
                                        dr=m-1;
                                        c2=m;
                                    }else
                                        st=m+1;
                                }
                                if(suma(1,c1+1,l1,c2)==v[j]&&exista(suma(1,c2+1,l1,n))){
                                    r[1]=suma(1,1,l1,c1);
                                    r[2]=suma(1,c1+1,l1,c2);
                                    r[3]=suma(1,c2+1,l1,n);
                                    r[4]=suma(l1+1,1,l2,c1);
                                    r[5]=suma(l1+1,c1+1,l2,c2);
                                    r[6]=suma(l1+1,c2+1,l2,n);
                                    r[7]=suma(l2+1,1,n,c1);
                                    r[8]=suma(l2+1,c1+1,n,c2);
                                    r[9]=suma(l2+1,c2+1,n,n);
                                    sort(r+1,r+10);
                                    for(k=1;k<=9;k++)
                                        if(v[k]!=r[k])
                                            k=11;
                                    if(k==10){
                                        printf("%d %d %d %d",l1,l2,c1,c2);
                                        return 0;
                                    }
                                }
                            }
                    }
                }
            }
          }
        }
    return 0;
}