Cod sursa(job #841125)

Utilizator stoicatheoFlirk Navok stoicatheo Data 23 decembrie 2012 20:06:24
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
#define MAX_N 520
#define FIN "zone.in"
#define FOUT "zone.out"
#define sum(x1, y1, x2, y2) (S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1])
#define mp make_pair
#define f first
#define s second
#define ll long long
 
int N, nv; ll S[MAX_N][MAX_N], A[9], V[9]; 
pair < pair<int, int>, pair<int, int> > sol;
 
int get_col(int i, int j, int k, ll s)
{
    int inc, l;
 
    for (inc = 1; inc < N; inc<<=1);
    for (l = j; inc; inc>>=1)
        if (l+inc <= N && sum(i, j, k, l+inc) <= s)
            l += inc;
    return sum(i, j, k, l) != s ? N+1 : l;
}
 
int get_line(int i, int j, int k, ll s)
{
    int inc, l;
 
    for (inc = 1; inc < N; inc<<=1);
    for (l = i; inc; inc>>=1)
        if (l+inc <= N && sum(i, j, l+inc, k) <= s)
            l += inc;
    return sum(i, j, l, k) != s ? N+1 : l;
}
 
int works(int l1, int l2, int c1, int c2)
{
    int i;
 
    nv = 0;
    V[nv++] = sum(1, 1, l1, c1);
    V[nv++] = sum(1, c1+1, l1, c2);
    V[nv++] = sum(1, c2+1, l1, N);
    V[nv++] = sum(l1+1, 1, l2, c1);
    V[nv++] = sum(l1+1, c1+1, l2, c2);
    V[nv++] = sum(l1+1, c2+1, l2, N);
    V[nv++] = sum(l2+1, 1, N, c1);
    V[nv++] = sum(l2+1, c1+1, N, c2);
    V[nv++] = sum(l2+1, c2+1, N, N);
 
    sort(V, V+nv);
    for (i = 0; i < nv; i++)
        if (V[i] != A[i]) return 0;
    return 1;
}
 
int main(void)
{
    int i, j, k, l1, l2, c1, c2;
 
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
 
    scanf("%d", &N);
    for (i = 0; i < 9; i++) scanf("%lld", A+i);
    sort(A, A+9);
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
        {
            scanf("%lld", S[i]+j);
            S[i][j] += S[i][j-1]+S[i-1][j]-S[i-1][j-1];
        }
 
    sol = mp(mp(N+1, N+1), mp(N+1, N+1));
    for (l1 = 1; l1 < N; l1++)
        for (i = 0; i < 9; i++)
        {   
            c1 = get_col(1, 1, l1, A[i]);
            if (c1 >= N) continue;
            for (j = 0; j < 9; j++)
            {
                if (i == j) continue;
                c2 = get_col(1, c1+1, l1, A[j]);
                if (c2 >= N) continue;
                for (k = 0; k < 9; k++)
                {
                    if (k == i || k == j) continue;
                    l2 = get_line(l1+1, 1, c1, A[k]);
                    if (l2 >= N) continue;
                    if (works(l1, l2, c1, c2) && sol > mp(mp(l1, c1), mp(l2, c2)))
                        sol = mp(mp(l1, c1), mp(l2, c2));
                }
            }
        }
 
    printf("%d %d %d %d\n", sol.f.f, sol.s.f, sol.f.s, sol.s.s);
 
    return 0;
}