Cod sursa(job #18929)

Utilizator filipbFilip Cristian Buruiana filipb Data 18 februarie 2007 14:58:19
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <stdio.h>
#include <assert.h>
#include <algorithm>
#define FOR(i, a, b) for (i = a; i <= b; i++)
#define INF 32000
#define ll long long
#define NMax 513

using namespace std;

int N, M[NMax][NMax];
ll S[NMax][NMax], SUM[9];

int l1 = INF, l2 = INF, c1 = INF, c2 = INF;

ll suma(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 check(int lin, ll S1, ll S2, ll S4)
{
     int i, l, r, m = 0;
     int ll1, ll2, cc1, cc2;
     ll S = 0, SF[9];
     
     ll1 = lin;
     // cautam a. i. sa avem in prima zona suma S1
     l = 1; r = N-2;
     while (l <= r)
     {
           m = (l + r) / 2;
           
           S = suma(1, 1, lin, m);
           if (S > S1) r = m-1; 
           else if (S < S1) l = m+1;
           else break;
     }
     if (S != S1) return ;
     cc1 = m;
          
     // cautam a. i. sa avem in a doua zona suma S2
     l = cc1+1; r = N-1;
     while (l <= r)
     {
           m = (l + r) / 2;
           
           S = suma(1, cc1+1, lin, m);
           if (S > S2) r = m-1; 
           else if (S < S2) l = m+1;
           else break;
     }
     if (S != S2) return ;     
     cc2 = m;
     
     // cautam a. i. sa avem in a patra zona suma S4

     l = lin+1; r = N-1;
     while (l <= r)
     {
           m = (l + r) / 2;
           
           S = suma(lin+1, 1, m, cc1);
           if (S > S4) r = m-1; 
           else if (S < S4) l = m+1;
           else break;
     }
     if (S != S4) return ;
     ll2 = m;
     
     // verificam daca cvadruplul (ll1, cc1, ll2, cc2) este intr-adevar solutie
     
     SF[0] = suma(1, 1, ll1, cc1);
     SF[1] = suma(1, cc1+1, ll1, cc2);
     SF[2] = suma(1, cc2+1, ll1, N);
     SF[3] = suma(ll1+1, 1, ll2, cc1);
     SF[4] = suma(ll1+1, cc1+1, ll2, cc2);
     SF[5] = suma(ll1+1, cc2+1, ll2, N);
     SF[6] = suma(ll2+1, 1, N, cc1);
     SF[7] = suma(ll2+1, cc1+1, N, cc2);
     SF[8] = suma(ll2+1, cc2+1, N, N);
          
     sort(SF+0, SF+9);
     for (i = 0; i < 9; i++)
         if (SF[i] != SUM[i])
            return ;
          
     if (ll1 < l1)
        l1 = ll1, c1 = cc1, l2 = ll2, c2 = cc2;
     else if (ll1 == l1 && cc1 < c1)
        l1 = ll1, c1 = cc1, l2 = ll2, c2 = cc2;
     else if (ll1 == l1 && cc1 == c1 && ll2 < l2)
        l1 = ll1, c1 = cc1, l2 = ll2, c2 = cc2;
     else if (ll1 == l1 && cc1 == c1 && ll2 == l2 && cc2 < c2)     
        l1 = ll1, c1 = cc1, l2 = ll2, c2 = cc2;
     
}

int main(void)
{
    int i, j, k, l;
    
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    
    scanf("%d", &N);
    
    assert(1 <= N && N <= 512);
    
    for (i = 0; i < 9; i++) scanf("%lld", &SUM[i]);
    
    sort(SUM+0, SUM+9);
    
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
        {
            scanf("%d", &M[i][j]);
            assert(1 <= M[i][j] && M[i][j] <= 10000000);
        }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + M[i][j];
    
    FOR (l, 1, N-1)
        FOR (i, 0, 8)
            FOR (j, 0, 8)
                if (i != j)
                   FOR (k, 0, 8)
                      if (k != i && k != j)
                         check(l, SUM[i], SUM[j], SUM[k]);
    
    printf("%d %d %d %d\n", l1, l2, c1, c2);
    
    return 0;
}