Cod sursa(job #1478894)

Utilizator andrettiAndretti Naiden andretti Data 29 august 2015 20:48:48
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
#include<stdio.h>
#include<algorithm>
#define maxn 515
using namespace std;

int n,lf1,lf2,cf1,cf2;
int a[maxn][maxn],used[15];
long long s[maxn][maxn],S[10],v[10];

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=9;i++)
     scanf("%lld",&S[i]);

    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      scanf("%d",&a[i][j]);
}

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

int bsearch_line(int L,int C,long long val)
{
    int i,step;
    for(step=1;step<n-C;step<<=1);

    for(i=C;step;step>>=1)
     if(i+step<n && s[L][i+step]-s[L][C]<=val)
      i+=step;

    if(s[L][i]-s[L][C]!=val) return -1;
    return i;
}

int bsearch_col(int C,int L,long long val)
{
    int i,step;
    for(step=1;step<n-L;step<<=1);

    for(i=L;step;step>>=1)
     if(i+step<n && s[i+step][C]-s[L][C]<=val)
      i+=step;

    if(s[i][C]-s[L][C]!=val) return -1;
    return i;
}

int check(long long val)
{
    for(int i=1;i<=9;i++)
     if(S[i]==val && !used[i])
         return 1;
    return 0;
}

long long Sum(int x1,int y1,int x2,int y2){
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

void mark(long long val,int ok)
{
    for(int i=1;i<=9;i++)
     if(S[i]==val && used[i]==!ok)
     {
         used[i]=ok;
         return;
     }
}

int final_check(int l1,int l2,int c1,int c2)
{
    int nrc=0;
    v[++nrc]=Sum(l1+1,c1+1,l2,c2);
    v[++nrc]=Sum(l1+1,c2+1,l2,n);
    v[++nrc]=Sum(l2+1,1,n,c1);
    v[++nrc]=Sum(l2+1,c1+1,n,c2);
    v[++nrc]=Sum(l2+1,c2+1,n,n);

    sort(v+1,v+6);
    int L=1;
    for(int i=1;i<=9 && L<=5;i++)
     if(!used[i])
      if(S[i]!=v[L]) return 0;
      else L++;

    if(L!=6) return 0;
    return 1;
}

void solve()
{
    int l1,l2,c1,c2;

    sort(S+1,S+10);

    for(l1=1;l1<n-1;l1++)
     for(int i=1;i<=9;i++) if(!used[i])
     {
         c1=bsearch_line(l1,0,S[i]);
         if(c1==-1 || c1>=n-1) continue;

         used[i]=1;
         for(int j=1;j<=9;j++) if(!used[j])
         {
             c2=bsearch_line(l1,c1,S[j]);
             if(c2==-1 || c2>n-1 || !check(s[l1][n]-s[l1][c2])) continue;

             used[j]=1; mark(s[l1][n]-s[l1][c2],1);
             for(int k=1;k<=9;k++) if(!used[k])
             {
                 l2=bsearch_col(c1,l1,S[k]);
                 if(l2==-1 || l2>n-1) continue;

                 used[k]=1;
                 if(final_check(l1,l2,c1,c2))
                 {
                     lf1=l1; lf2=l2;
                     cf1=c1; cf2=c2;
                     return;
                 }
                 used[k]=0;
             }
             used[j]=0; mark(s[l1][n]-s[l1][c2],0);
         }
         used[i]=0;
     }
}

int main()
{
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);

    read();
    preproc();
    solve();
    printf("%d %d %d %d",lf1,lf2,cf1,cf2);

    fclose(stdin);
    fclose(stdout);
    return 0;
}