Cod sursa(job #3322676)

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

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

int cbin(long long x, int st, int dr) // ← tip corectat
{
    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-2; i++)          // ← limite corectate
        for (int j = 1; j <= n-2; j++)      // ← limite corectate
        {
            p1x = i;
            p1y = j;
            long long saux = sump[p1x][p1y]; // ← tip corectat

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

                    for (int q = j+1; q <= n-1 && gasit == 1; q++) // ← limite corectate
                    {
                        p2x = p;
                        p2y = q;

                        s[1] = sump[i][j];
                        s[2] = sump[i][q] - sump[i][j];
                        s[3] = sump[i][n] - sump[i][q];
                        s[4] = sump[p][j] - sump[i][j];
                        s[5] = sump[p][q] - sump[i][q] - sump[p][j] + sump[i][j];
                        s[6] = sump[p][n] - sump[i][n] - sump[p][q] + sump[i][q];
                        s[7] = sump[n][j] - sump[p][j]; // ← zona 7 corectă
                        s[8] = sump[n][q] - sump[p][q] - sump[n][j] + sump[p][j];
                        s[9] = sump[n][n] - sump[p][n] - sump[n][q] + sump[p][q];

                        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 ||
                                i < lr1 ||
                                (i == lr1 && j < cr1) ||
                                (i == lr1 && j == cr1 && p < lr2) ||
                                (i == lr1 && j == cr1 && p == lr2 &&
                                 i + p + j + q < lr1 + lr2 + cr1 + cr2))
                            {
                                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;
}