Cod sursa(job #3285558)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 13 martie 2025 10:11:50
Problema Zone Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("zone.in");
ofstream fout("zone.out");
long long n, i, j, sumPart[602][602], sum[112];
long long lin[5], col[5];
bool fr[12];

static inline int Exista(long long val) {
    for(i = 1; i <= 9; i++) {
        if(!fr[i] && sum[i] == val) return i;
    }
    return 0;
}

static inline bool Verif(int lin1, int col1, int lin2, int col2) {
    lin[1] = lin1;
    lin[2] = lin2;
    lin[3] = n;

    col[1] = col1;
    col[2] = col2;
    col[3] = n;

    memset(fr, false, sizeof(fr));
    for(int i = 1; i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            long long s1 = sumPart[lin[i]][col[j]];
            long long s2 = sumPart[lin[i - 1]][col[j]];
            long long s3 = sumPart[lin[i]][col[j - 1]];
            long long s4 = sumPart[lin[i - 1]][col[j - 1]];

            long long sumCur = s1 - s2 - s3 + s4;

            int e = Exista(sumCur);
            if(e == 0 || fr[e]) return false;
            fr[e] = true;
        }
    }
    return true;
}

static inline void Calc() {
    int i, j, k, l;
    bool ok = false;

    for(i = 1; i < n && !ok; i++) {
        for(j = 1; j < n && !ok; j++) {
            if(!Exista(sumPart[i][j])) continue;

            for(k = i + 1; k < n && !ok; k++) {
                for(l = j + 1; l < n && !ok; l++) {
                    ok = Verif(i, j, k, l);
                }
            }
        }
    }
}

int main() {
    fin >> n;
    for(i = 1; i <= 9; i++) fin >> sum[i];

    sort(sum + 1, sum + 10);

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

    Calc();

    fout << lin[1] << " " << lin[2] << " ";
    fout << col[1] << " " << col[2];

    return 0;
}