Cod sursa(job #1503669)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 16 octombrie 2015 18:34:16
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <cstdio>
#define NMAX 520
long long val[10],sum[NMAX][NMAX];
int n;
bool vis[10];
int gas(long long nr)
{
    for(int i=1;i<=9;i++)
    {
        if(vis[i]==0&&val[i]==nr)
        {
            vis[i]=1;
            return 1;
        }
    }
    return 0;
}
void reset(long long nr)
{
    for(int i=1;i<=9;i++)
    {
        if(vis[i]==1&&val[i]==nr)
        {
            vis[i]=0;
            return;
        }
    }
}
int main()
{
    freopen ("zone.in","r",stdin);
    freopen ("zone.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=9;i++) scanf("%lld",&val[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&sum[i][j]);
            sum[i][j]+=(sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]);
        }
    }
    bool as=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(gas(sum[i][j])==1)
            {
                for(int k=i+1;k<=n;k++)
                {
                    if(gas(sum[k][j]-sum[i][j])==1&&gas(sum[n][j]-sum[k][j])==1)
                    {
                        for(int s=j+1;s<=n;s++)
                        {
                            if(gas(sum[i][s]-sum[i][j])==1&&gas(sum[i][n]-sum[i][s])==1)
                            {
                                if(gas(sum[k][s]-sum[i][s]-sum[k][j]+sum[i][j])==1&&gas(sum[k][n]-sum[i][n]-sum[k][s]+sum[i][s])==1)
                                {
                                    if(gas(sum[n][s]-sum[k][s]-sum[n][j]+sum[k][j])==1&&gas(sum[n][n]-sum[k][n]-sum[n][s]+sum[k][s])==1)
                                    {
                                       // if(i==1&&j==2&&k==3&&s==3) printf("AA");
                                        printf("%d %d %d %d\n",i,s,j,k);
                                        as=1;
                                        break;
                                    }
                                    reset(sum[n][s]-sum[k][j]-sum[n][i]+sum[k][j]);
                                    reset(sum[n][n]-sum[k][n]-sum[n][s]+sum[k][s]);
                                }
                                reset(sum[k][s]-sum[i][s]-sum[k][j]+sum[i][j]);
                                reset(sum[k][n]-sum[i][n]-sum[k][s]+sum[i][s]);
                            }
                            reset(sum[i][s]-sum[i][j]);
                            reset(sum[i][n]-sum[i][j]);
                        }
                        if(as==1) break;
                    }
                    reset(sum[k][j]-sum[i][j]);
                    reset(sum[n][j]-sum[k][j]);
                }
            }
            if(as==1) break;
            reset(sum[i][j]);
        }
        if(as==1) break;
    }
}