Cod sursa(job #961066)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:48:17
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.47 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *fin=fopen("zone.in","r");
FILE *fout=fopen("zone.out","w");
 
long long n,v[11],x[10],y[10],a[514][514],l1,l2,c1,c2,val,p,u,ok,s;
 
 
long long apartine(long long s){
    for(long long i = 1; i<=9; i++){
        if(s==v[i]){
            return i;
        }
    }
return -1; 
}
long long verificare(long long l1, long long l2, long long c1, long long c2){
    long long u;
    u=0;
    for(long long i = 1 ; i<=9; i++){
        if(v[i]>0){
            x[++u]=v[i];
        }
    }
    y[1]=a[l1][n]-a[l1][c2];
    y[2]=a[l2][c2]-a[l2][c1]-a[l1][c2]+a[l1][c1];
    y[3]=a[l2][n]-a[l2][c2]-a[l1][n]+a[l1][c2];
    y[4]=a[n][c1]-a[l2][c1];
    y[5]=a[n][c2]-a[n][c1]-a[l2][c2]+a[l2][c1];
    y[6]=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
     
    sort(x+1,x+7);
    sort(y+1,y+7);
     
    for(long long i = 1; i<=6; i++){
        if(x[i]!=y[i]){
            return 0;
        }
    }
     
    fprintf(fout,"%lld %lld %lld %lld",l1,l2,c1,c2);
     
return 1;
}
int main(){
     
    fscanf(fin,"%lld",&n);
     
    for(long long i = 1; i<=9; i++){
        fscanf(fin,"%lld",&v[i]);
    }
     
    sort(v+1,v+10);
     
    for(long long i = 1; i<=n; i++){
        for(long long j = 1; j<=n; j++){
            fscanf(fin,"%lld",&val);
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+val;
        }
    }
     
    for(long long l1 = 1; l1<=n-1; l1++){
         
        for(long long s1 = 1; s1<=9; s1++){
             
            p=1;
            u=n;
            ok=0;
            while(p<=u){
                c1=(p+u)/2;
                 
                s=a[l1][c1];
                if(s==v[s1]){
                    ok=1;
                    break;
                }
                if(s<v[s1]){
                    p=c1+1;
                }
                else{
                    u=c1-1;
                }
            }
             
            if(ok==1){
                v[s1]=-v[s1];
                 
                p=l1+1;
                u=n;
                ok=0;
                 
                for(long long s2=1;s2<=9; s2++){
                     
                    p=l1+1;
                    u=n;
                    ok=0;
                    while(p<=u){
                        l2=(p+u)/2;
                         
                        s=a[l2][c1]-a[l1][c1];
                         
                        if( s==v[s2] ){
                            ok=1;
                            break;
                        }
                        if(s<v[s2]){
                            p=l2+1;
                        }
                        else{
                            u=l2-1;
                        }
                         
                    }
                     
                    if(ok==1){
                        v[s2]=-v[s2];
                         
                        for(long long s3=1; s3<=9; s3++){
                             
                            p=c1+1;
                            u=n;
                            ok=0;
                             
                            while(p<=u){
                                 
                                c2=(p+u)/2;
                                s=a[l1][c2]-a[l1][c1];
                                 
                                if(s==v[s3]){
                                    v[s3]=-v[s3];
                                    ok=verificare(l1,l2,c1,c2);
                                    v[s3]=-v[s3];
                                    if(ok) return 0;
                                    break;
                                }
                                if(s<v[s3]){
                                    p=c2+1;
                                }
                                else{
                                    u=c2-1;
                                }
                                 
                            }
                             
                             
                             
                             
                        }// for s3
                         
                         
                        v[s2]=-v[s2];
                    }
                     
                }// for s2
                 
                v[s1]=-v[s1];
            }
             
        }// for s1
         
         
    }
     
     
    return 0;
}