Cod sursa(job #2481212)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 26 octombrie 2019 16:47:29
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.02 kb
#include <iostream>
#include <fstream>
#include <vector>

typedef long long int int64;

using namespace std;

ifstream in("zone.in");
ofstream out("zone.out");

int64 m[514][514], mpsum[514][514];
int64 sums[9];
bool sel_sums[9];
int64 n;

struct quadruple {
    int64 x, y, z, w;
    quadruple(int64 a, int64 b, int64 c, int64 d): x(a), y(b), z(c), w(d) {};
    bool operator<(quadruple &B) {
        if (x < B.x)
            return true;
        if (x > B.x)
            return false;
        if (y < B.y)
            return true;
        if (y > B.y)
            return false;
        if (z < B.z)
            return true;
        if (z > B.z)
            return false;
        if (w <= B.w)
            return true;
        return false;
    }
};

int64 submat(int64 i1, int64 j1, int64 i2, int64 j2) {
    return mpsum[i2][j2] - mpsum[i2][j1 - 1] - mpsum[i1 - 1][j2] + mpsum[i1 - 1][j1 - 1];
}

int64 find_cr(bool col, int64 csum, int64 bound_left, int64 bound_right, int64 i1, int64 j1, int64 k2) {
    int64 left = bound_left, right = bound_right, middle, subsum;
    while (left <= right) {
        middle = left + (right - left) / 2;
        if (col)
            subsum = submat(i1, j1, k2, middle);
        else
            subsum = submat(i1, j1, middle, k2);
        if (subsum == csum)
            return middle;
        else if (subsum < csum)
            left = middle + 1;
        else
            right = middle - 1;
    }
    return -1ll;
}

int main() {
    in >> n;
    for (int64 i = 0; i < 9; i++) {
        in >> sums[i];
    }
    for (int64 i = 1; i <= n; i++) {
        for (int64 j = 1; j <= n; j++) {
            in >> m[i][j];
            mpsum[i][j] = m[i][j] + mpsum[i][j - 1] + mpsum[i - 1][j] - mpsum[i - 1][j - 1];
        }
    }

    quadruple sol(514, 514, 514, 514);
    int64 csum, l1, l2, c1, c2;
    for (int64 i = 0; i < 9; i++) {
        csum = sums[i];

        // cautare submatrice 1
        for (l1 = 1; l1 <= n - 2; l1++) {
            if (csum < submat(1, 1, l1, 1))
                break;
            c1 = find_cr(true, csum, 1, n - 2, 1, 1, l1);
            if (c1 == -1ll)
                continue;

            // am gasit o pereche valida l1 c1, continuam similar pentru gasirea lui c2
            // cout << csum << ' ' << l1 << ' ' << c1 << '\n';
            for (int64 j = 0; j < 9; j++) {
                if (i != j) {
                    csum = sums[j];
                    if (csum < submat(1, c1 + 1, l1, c1 + 1))
                        break;
                    c2 = find_cr(true, csum, c1 + 1, n - 1, 1, c1 + 1, l1);
                    if (c2 == -1ll)
                        continue;

                    // am gasit c2 valid, continuam simetric pentru a verifica validitatea unui l2
                    //cout << '\t' << csum << ' ' << l1 << ' ' << c2 << '\n';
                    for (int64 k = 0; k < 9; k++) {
                        if (k != i && k != j) {
                            csum = sums[k];
                            if (csum < submat(l1 + 1, 1, l1 + 1, c1))
                                break;
                            l2 = find_cr(false, csum, l1 + 1, n - 1, l1 + 1, 1, c1);
                            if (l2 == -1ll)
                                continue;
                            exit(2);
                            //cout << "\t\t" << csum << ' ' << l1 << ' ' << c1 << ' ' << l2 << ' ' << c2 << '\n';
                            
                            // am gasit cei 4 indici cu sumele in pozitiile i, j si k
                            // verificam daca putem atribui zonelor ramase una din celelalte 6 sume
                            sel_sums[i] = sel_sums[j] = sel_sums[k] = true;
                            int64 sum[6], nr = 3;
                            sum[0] = submat(1, c2 + 1, l1, n);
                            sum[1] = submat(l1 + 1, c1 + 1, l2, c2);
                            sum[2] = submat(l1 + 1, c2 + 1, l2, n);
                            sum[3] = submat(l2 + 1, 1, n, c1);
                            sum[4] = submat(l2 + 1, c1 + 1, n, c2);
                            sum[5] = submat(l2 + 1, c2 + 1, n, n);
                            for (int64 p = 0; p < 6; p++) {
                                for (int64 q = 0; q < 9; q++) {
                                    if (sum[p] == sums[q] && !sel_sums[q]) {
                                        sel_sums[q] = true;
                                        nr++;
                                    }
                                }
                            }
                            quadruple curr(l1, c1, l2, c2);
                            if (nr == 9 && curr < sol)
                               sol = curr;
                            for (int I = 0; I < 9; I++)
                                sel_sums[I] = false;
                        }
                    }
                }
            }
        }
    }
    out << sol.x << ' ' << sol.z << ' ' << sol.y << ' ' << sol.w << '\n';
    return 0;
}