Cod sursa(job #2481307)

Utilizator mirunazMiruna Zavelca mirunaz Data 26 octombrie 2019 18:37:15
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("zone.in");
ofstream out("zone.out");
#define N 513
#define M 9
int a[N][N], zona[M];

bool find(int x) {
    for (int i : zona) {
        if (i == x)  return true;
    }
    return false;
}

int sum(int l1, int c1, int l2, int c2) {
    return a[l2][c2] - a[l1][c2] + a[l1][c1] - a[l2][c1];
}

bool verif(int p[]) {
    for (int i = 0; i < M; i ++ ) {
        if (p[i] != zona[i])    return false;
    }
    return true;
}

void solve(int n) {
    int p[M];
    for (int l1 = 1; l1 < n; l1 ++) {
        for (int c1 = 1; c1 < n; c1 ++) {
            if (find(a[l1][c1])) {
                for (int l2 = l1 + 1; l2 <= n; l2 ++) {
                    if(find(a[l2][c1] - a[l1][c1]) && find(a[n][c1] - a[l2][c1])) {
                        for (int c2 = c1 + 1; c1 <= n; c1 ++) {
                            if(find(a[l1][c2] - a[l1][c1]) && find(a[l1][n] - a[l1][c2])) {
                                p[1] = a[l1][c1];
                                p[2] = a[l1][c2] - a[l1][c1];
                                p[3] = a[l1][n] - a[l1][c2];
                                p[4] = a[l2][c1] - a[l1][c1];
                                p[5] = sum(l1, c1, l2, c2);
                                p[6] = sum(l1, c2, l2, n);
                                p[7] = a[n][c1] - a[l2][c1];
                                p[8] = sum(l2, c1, n, c2);
                                p[0] = sum(l2, c2, n, n);
                                sort (p, p + M);
                                if (verif(p)) {
                                    out << l1  << ' ' << l2 << ' ' << c1 << ' ' << c2;
                                    return ;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    int n;
    in >> n;
    for (int i = 0; i < M; i ++) {
        in >> zona[i];
    }
    sort(zona, zona + 9);

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            in >> a[i][j];
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }

    solve(n);
    return 0;
}