Cod sursa(job #1305749)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 30 decembrie 2014 03:01:52
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <vector>

#include <cstdio>
using namespace std;

#define getSum(x1, y1, x2, y2) S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1]

const int MAX_N = 520;

int N;
int A[MAX_N][MAX_N];
long long S[MAX_N][MAX_N], v[10], w[10];
vector < pair < int, int > > a, b;

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

    scanf("%d", &N);;
    for(int i = 1; i <= 9; ++i)
        scanf("%lld", &v[i]);

    for(int i = 1; i < 9; ++i)
        for(int j = i + 1; j <= 9; ++j)
            if(v[i] > v[j])
                swap(v[i], v[j]);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            scanf("%d", &A[i][j]);

            S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + A[i][j];
        }

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            long long s = getSum(1, 1, i, j);

            for(int k = 1; k <= 9; ++k)
                if(s == v[k])
                    a.push_back(make_pair(i, j)), k = 9;

            if(i == N || j == N)
                continue;

            s = getSum(i + 1, j + 1, N, N);
            for(int k = 1; k <= 9; ++k)
                if(s == v[k])
                    b.push_back(make_pair(i, j)), k = 9;
        }


    for(int i = 0; i < (int) a.size(); ++i)
        for(int j = 0; j < (int) b.size(); ++j) {
            int x1 = a[i].first, y1 = a[i].second, x2 = b[j].first, y2 = b[j].second;

            if(x1 >= x2 || y1 >= y2)
                continue;

            long long s1 = getSum(1, 1, x1, y1), s2 = getSum(x2 + 1, y2 + 1, N, N);

            if(s1 == s2) {
                int cnt = 0;

                for(int k = 1; k <= 9; ++k)
                    if(v[k] == s1)
                        ++cnt;

                if(cnt < 2)
                    continue;
            }

            w[1] = s1;
            w[2] = getSum(1, y1 + 1, x1, y2);
            w[3] = getSum(1, y2 + 1, x1, N);
            w[4] = getSum(x1 + 1, 1, x2, y1);
            w[5] = getSum(x1 + 1, y1 + 1, x2, y2);
            w[6] = getSum(x1 + 1, y2 + 1, x2, N);
            w[7] = getSum(x2 + 1, 1, N, y1);
            w[8] = getSum(x2 + 1, y1 + 1, N, y2);
            w[9] = s2;

            for(int k = 1; k < 9; ++k)
                for(int h = k + 1; h <= 9; ++h)
                    if(w[k] > w[h])
                        swap(w[k], w[h]);

            bool ok = 1;
            for(int k = 1; k <= 9; ++k)
                if(v[k] != w[k])
                    ok = 0, k = 9;

            if(ok) {
                printf("%d %d %d %d\n", x1, x2, y1, y2);

                i = a.size();
                j = b.size();
            }
        }

    return 0;
}