Cod sursa(job #360858)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 2 noiembrie 2009 13:59:51
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 513
#define LL long long    // NU UITA
using namespace std;

LL s[Nmax][Nmax];
LL z[10];
int a[Nmax][Nmax],use[10];
int n,i1,col1,col2,i2;

void read(){
	int i,j;
	freopen("zone.in","r",stdin);
   freopen("zone.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<10;++i) scanf("%lld",&z[i]);
   sort(z+1,z+10);
   for(i=1;i<=n;++i)
     for(j=1;j<=n;++j) scanf("%d",&a[i][j]);

   for(i=1;i<=n;++i)
     for(j=1;j<=n;++j)
       s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
}

int caut_bin(int l,int r,LL x){
	int m;
   while(l<=r){
   	m=l+(r-l)/2;
      if(s[i1][m]-s[i1][col1] == x) return m;
      if( s[i1][m]-s[i1][col1] < x) l=m+1;
      else r=m-1;
   }
   return -1;
}

int caut_bin2(LL x){
	int m,l=1,r=9,ret=-1;
   while(l<=r){
   	m=l+(r-l)/2;
      if(z[m] == x){ ret=m; r=m-1; }
      else if(z[m] > x) r=m-1;
     		  else l=m+1;

   }
   if( ret != -1 ) use[ret]=1;
   return ret;
}

int search(){
	int i,p1,p2,p3,p4,p5,p6; LL z1,z2,z3,z4,z5,z6;
   for(i=i1+1;i<=n;++i){
   	z1 = s[i][col1] - s[i1][col1];
   	p1 = caut_bin2(z1);
      if( p1 != -1){
      	z2 = s[i][col2] - s[i][col1] - s[i1][col2] + s[i1][col1];
         p2 = caut_bin2(z2);
         if( p2 != -1){
     			 z3 = s[i][n] - s[i][col2] - s[i1][n] + s[i1][col2];
             p3 = caut_bin2(z3);
             if( p3 != -1){
      				z4 = s[n][col1] - s[i][col1];
                  p4 = caut_bin2(z4);
                  if( p4 != -1){
      					  z5 = s[n][col2] - s[n][col1]- s[i][col2] + s[i][col1];
                       p5 = caut_bin2(z5);
                       if( p5 != -1){
      							 z6 = s[n][n] - s[n][col2] - s[i][n] + s[i][col2];
                            p6 = caut_bin2(z6);
                            if( p6 != -1 ){ i2=i; return 1; }
                            use[p6]=0;
                       }
                       use[p5]=0;
                  }
                  use[p4]=0;
             }
             use[p3]=0;
         }
         use[p2]=0;
      }
      use[p1]=0;
   }
   return 0;
}

void solve(){
	int i,j,poz; LL suma3;
   for(i1=1;i1<=n;++i1)
  		 for(i=1; i<=9; ++i){ // caut prima zona cu suma z[i1]
       		use[i]=1;
       		col1=caut_bin(1,n,z[i]);
            if(col1 != -1){
            	for(j=1;j<=9;++j)
                 if(!use[j]){
                 		use[j]=1;
                 		col2=caut_bin(col1+1,n,z[j]);
                     if(col2 != -1){
                        suma3= s[i1][n]-s[i1][col2];
                        poz = caut_bin2(suma3);
                        if( poz!=-1 ){
                          	if( search() ) return;
                           use[poz]=0;
                        }
                     }
                     use[j]=0;
                 }
            }
            use[i]=0;
       }
}

int main(){
	read();
   solve();

   printf("%d %d %d %d\n",i1,i2,col1,col2);
   fclose(stdin); fclose(stdout);
   return 0;
}