Cod sursa(job #3312880)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 30 septembrie 2025 17:10:53
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double
#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

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

const int NMAX = 512;

int n;
int a[9];
int sp[NMAX + 1][NMAX + 1];

int get_sum(int i1, int j1, int i2, int j2) {
    return sp[i2][j2] - sp[i1 - 1][j2] - sp[i2][j1 - 1] + sp[i1 - 1][j1 - 1];
}

bool is_good(int i1, int j1, int i2, int j2) {
    int v[9];
    v[0] = get_sum(1, 1, i1, j1);
    v[1] = get_sum(1, j1 + 1, i1, j2);
    v[2] = get_sum(1, j2 + 1, i1, n);
    v[3] = get_sum(i1 + 1, 1, i2, j1);
    v[4] = get_sum(i1 + 1, j1 + 1, i2, j2);
    v[5] = get_sum(i1 + 1, j2 + 1, i2, n);
    v[6] = get_sum(i2 + 1, 1, n, j1);
    v[7] = get_sum(i2 + 1, j1 + 1, n, j2);
    v[8] = get_sum(i2 + 1, j2 + 1, n, n);

    sort(v, v + 9);
    for(int i = 0; i < 9; i++) {
        if(v[i] != a[i]) {
            return false;
        }
    }
    return true;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fin >> n;
    for(int i = 0; i < 9; i++) {
        fin >> a[i];
    }
    sort(a, a + 9);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int x;
            fin >> x;
            sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + x;
        }
    }

    for(int i1 = 1; i1 < n; i1++) {
        for(int j1 = 1; j1 < n; j1++) {
            if(!binary_search(a, a + 9, sp[i1][j1])) {
                continue;
            }

            for(int i2 = i1 + 1; i2 <= n; i2++) {
                if(!binary_search(a, a + 9, get_sum(i1 + 1, 1, i2, j1))) {
                    continue;
                }

                for(int j2 = j1 + 1; j2 <= n; j2++) {
                    if(is_good(i1, j1, i2, j2)) {
                        fout << i1 << ' ' << i2 << ' ' << j1 << ' ' << j2 << '\n';
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}