Cod sursa(job #3322685)

Utilizator Mike_RossMIke Ross Mike_Ross Data 15 noiembrie 2025 11:06:32
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zone.in");
ofstream cout ("zone.out");

int n;
long long sume[10];
long long a[515][515];
long long sump[515][515];
long long s[10];
bool amsolutie = 0;
int lr1, lr2, cr1, cr2;

int cbin(long long x, int st, int dr)
{
    while (st <= dr)
    {
        int mij = (st + dr) / 2;
        if (sume[mij] == x)
            return 1;
        if (sume[mij] < x)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    return 0;
}

int verif(int &l1, int &l2, int &c1, int &c2)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            long long saux = sump[i][j];

            if (cbin(saux, 1, 9) == 1)
            {
                for (int p = i + 1; p <= n; p++)
                {
                    bool gasit = 1;

                    for (int q = j + 1; q <= n && gasit == 1; q++)
                    {
                        // --- FORMULELE CORECTE ALE CELOR 9 ZONE ---
                        s[1] = sump[i][j];
                        s[2] = sump[i][q] - s[1];
                        s[3] = sump[i][n] - s[1] - s[2];

                        s[4] = sump[p][j] - s[1];
                        s[5] = sump[p][q] - s[1] - s[2] - s[4];
                        s[6] = sump[p][n] - s[1] - s[2] - s[3] - s[4] - s[5];

                        s[7] = sump[n][j] - s[1] - s[4];
                        s[8] = sump[n][q] - s[1] - s[2] - s[4] - s[5] - s[7];
                        s[9] = sump[n][n] - (s[1] + s[2] + s[3] +
                                             s[4] + s[5] + s[6] +
                                             s[7] + s[8]);
                        // --------------------------------------------------

                        sort(s + 1, s + 10);

                        for (int f = 1; f <= 9; f++)
                            if (s[f] != sume[f])
                            {
                                gasit = 0;
                                break;
                            }

                        if (gasit == 1)
                        {
                            if (amsolutie == 0)
                            {
                                l1 = i;
                                l2 = p;
                                c1 = j;
                                c2 = q;
                                lr1 = i;
                                lr2 = p;
                                cr1 = j;
                                cr2 = q;
                                amsolutie = 1;
                            }
                        }
                    }
                }
            }
        }
    return 0;
}

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

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

    sort(sume + 1, sume + 10);

    int a = 0, b = 0, c = 0, d = 0;
    verif(a, b, c, d);

    cout << lr1 << ' ' << lr2 << ' ' << cr1 << ' ' << cr2;

    return 0;
}