Cod sursa(job #19576)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 19 februarie 2007 19:30:31
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxl 10
#define maxn 510
#define ll long long

int n;
ll sum[maxl],b[maxl];
ll s[maxn][maxn];

int find1(ll x,int y,int a,int b)
{
    int front=a,middle,back=b,aux=-1;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
          if (s[y][middle]>=x) 
          {
              aux=middle;
              back=middle-1;
          }
          else front=middle+1;
    }
    
    if ((aux==-1) || (s[y][aux]!=x)) return -1;
    return aux;
}

int find2(ll x,int y,int a,int b)
{
    int front=a,middle,back=b,aux=-1;
    
    while (front<=back)
    {
          middle=(front+back)/2;
          
          if (s[middle][y]>=x)
          {
              aux=middle;
              back=middle-1;
          }
		  else front=middle+1;
    }
    
    if ((aux==-1) || (s[aux][y]!=x)) return -1;
    return aux;
}

int OK(int x,int y,int z,int t)
{
    int i;
    
    b[1]=s[x][y];
    b[2]=s[x][t]-s[x][y];
    b[3]=s[x][n]-s[x][t];
    b[4]=s[z][y]-s[x][y];
    b[5]=s[z][t]-s[x][t]-s[z][y]+s[x][y];
    b[6]=s[z][n]-s[x][n]-s[z][t]+s[x][t];
    b[7]=s[n][y]-s[z][y];
    b[8]=s[n][t]-s[n][y]-s[z][t]+s[z][y];
    b[9]=s[n][n]-s[n][t]-s[z][n]+s[z][t];
    
    sort(b+1,b+maxl);
    for (i=1;i<maxl;i++) 
      if (b[i]!=sum[i]) return 0;
      
    return 1;
}

int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);
    
    scanf("%d ",&n);
    int i,j,k,p,x,y,z;
    
    for (i=1;i<maxl;i++) scanf("%lld",&sum[i]);
    
    sort(sum+1,sum+maxl);
       
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
      {
          scanf("%d",&x);
          s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
      }
         
    for (i=1;i<maxl;i++)  
      for (j=0;j<n;j++)  
      {
          x=find1(sum[i],j,0,n-1);
          if (x!=-1)
            for (k=1;k<maxl;k++) 
              if (k!=i)
              {
                   y=find2(sum[k]+sum[i],x,j+1,n-1);
				   if (y!=-1)
                   for (p=1;p<maxl;p++)
                     if ((p!=i) && (p!=k))
                     {                                
                          z=find1(sum[p]+sum[i],j,x+1,n-1);
                          if ((z!=-1) && OK(j,x,y,z))
                          {
                              printf("%d %d %d %d\n",j,y,x,z);
                              return 0;
                          }
                     } 
              }
      }
      
    while (true) n=n;
    
    return 0;
}