Cod sursa(job #1774065)

Utilizator silkMarin Dragos silk Data 8 octombrie 2016 15:21:14
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMax 512
#define ll long long
using namespace std;

ll sum[NMax+1][NMax+1];
ll zone[10];
ll temp[10];
int v[NMax+1][NMax+1];
int atins[10];
int sol,N,l1,l2,c1,c2;
int s1,s2,s3,s4;

ll get_sum(int i, int j, int ii, int jj)
{
    return sum[ii][jj] - sum[i-1][jj] - sum[ii][j-1] + sum[i-1][j-1];
}

void ok()
{
    temp[1] = get_sum(1,1,l1,c1);
    temp[2] = get_sum(1,c1+1,l1,c2);
    temp[3] = get_sum(1,c2+1,l1,N);
    temp[4] = get_sum(l1+1,1,l2,c1);
    temp[5] = get_sum(l1+1,c1+1,l2,c2);
    temp[6] = get_sum(l1+1,c2+1,l2,N);
    temp[7] = get_sum(l2+1,1,N,c1);
    temp[8] = get_sum(l2+1,c1+1,N,c2);
    temp[9] = get_sum(l2+1,c2+1,N,N);

    sort(temp+1,temp+10);
    for(int i = 1; i <= 9; ++i)
    if( zone[i] ^ temp[i] ) return;

    if( s2 > l2 ) { s2 = l2; s4 = c2; }
    else if( s2 == l2 && s4 > c2 ) s4 = c2;
    s1 = l1;
    s3 = c1;
    sol = 1;
}

bool is(int x)
{
    for(int i = 1; i <= 9; ++i)
    if( !atins[i] && zone[i] == x ) { atins[i] = 1; return 1; }
    return 0;
}

void Search_l2()
{
    int st,dr,mid,i,find;
    for(i = 1; i <= 9; ++i)
    if( !atins[i] )
    {
        atins[i] = 1;
        find = 0;
        for(st = l1+1, dr = N-1; st <= dr; )
        {
            mid = (st+dr)/2;
            if( get_sum(l1+1,1,mid,c1) > zone[i] ) dr = mid - 1;
            else if( get_sum(l1+1,1,mid,c1) < zone[i] ) st = mid + 1;
            else { l2 = mid; find = 1; break; }
        }

        if( find ) ok();
        atins[i] = 0;
    }
}

void Search_c2()
{
    int st,dr,mid,i,find;
    for(i = 1; i <= 9; ++i)
    if( !atins[i] )
    {
        atins[i] = 1;
        find = 0;
        for(st = c1+1, dr = N-1; st <= dr; )
        {
            mid = (st+dr)/2;
            if( get_sum(1,c1+1,l1,mid) > zone[i] ) dr = mid - 1;
            else if( get_sum(1,c1+1,l1,mid) < zone[i] ) st = mid + 1;
            else { c2 = mid; find = 1; break; }
        }

        if( find ) Search_l2();
        atins[i] = 0;
    }
}

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

    int i,j;

    scanf("%d",&N);
    for(i = 1; i <= 9; ++i) scanf("%d", &zone[i]);
    sort(zone+1,zone+10);

    for(i = 1; i <= N; ++i)
        for(j = 1; j <= N; ++j)
        {
            scanf("%d",&v[i][j]);
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + v[i][j];
        }

    s2 = s4 = NMax+1;
    for(l1 = 1; l1 <= N-2; ++l1)
        for(c1 = 1; c1 <= N-2; ++c1)
        if( is( sum[l1][c1] ) )
        {
            Search_c2();

            if(sol) { c1 = l1 = N+1; }
            memset(atins, 0, sizeof(atins));
        }


    printf("%d %d %d %d\n",s1,s2,s3,s4);




return 0;
}