Cod sursa(job #1305744)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 30 decembrie 2014 02:50:09
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 520;

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

inline int getSum(int x1, int y1, int x2, int y2) {
    return S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1];
}

int main() {
    ifstream f("zone.in");
    ofstream g("zone.out");

    f >> N;
    for(int i = 1; i <= 9; ++i)
        f >> v[i];
    sort(v + 1, v + 10);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j) {
            f >> 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) {
            int 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;

            int 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;

            sort(w + 1, w + 10);

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

            if(ok) {
                g << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";

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

    f.close();
    g.close();

    return 0;
}