Cod sursa(job #1339085)

Utilizator zombacDica Razvan zombac Data 10 februarie 2015 17:50:56
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin ("zone.in");
ofstream fout ("zone.out");
int N, l1, c1, l2, c2, sol1, sol2, sol3, sol4, b[10], V[530][530];
long long V9[10], S[530][530];

bool Caut_Binar(int val)
{
    int st = 1, dr = 9, mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (V9[mij] < val) st = mij + 1;
        else if (V9[mij] > val) dr = mij - 1;
        else return 1;
    }
    return 0;
}

long long Sum(int i1, int j1, int i2, int j2)
{
    return (S[i1-1][j1-1] + S[i2][j2] - S[i1-1][j2] - S[i2][j1-1]);
}

bool Verif()
{
    if (!Caut_Binar(Sum(1, 1, l1, c1))) return 0;
    else b[1] = Sum(1, 1, l1, c1);

    if (!Caut_Binar(Sum(1, c1+1, l1, c2))) return 0;
    else b[2] = Sum(1, c1+1, l1, c2);

    if (!Caut_Binar(Sum(1, c2+1, l1, N))) return 0;
    else b[3] = Sum(1, c2+1, l1, N);

    if (!Caut_Binar(Sum(l1+1, 1, l2, c1))) return 0;
    else b[4] = Sum(l1+1, 1, l2, c1);

    if (!Caut_Binar(Sum(l1+1, c1+1, l2, c2))) return 0;
    else b[5] = Sum(l1+1, c1+1, l2, c2);

    if (!Caut_Binar(Sum(l1+1, c2+1, l2, N))) return 0;
    else b[6] = Sum(l1+1, c2+1, l2, N);

    if (!Caut_Binar(Sum(l2+1, 1, N, c1))) return 0;
    else b[7] = Sum(l2+1, 1, N, c1);

    if (!Caut_Binar(Sum(l2+1, c1+1, N, c2))) return 0;
    else b[8] = Sum(l2+1, c1+1, N, c2);

    if (!Caut_Binar(Sum(l2+1, c2+1, N, N))) return 0;
    else b[9] = Sum(l2+1, c2+1, N, N);

    sort (b + 1, b + 10);
    for (int i = 1; i <= 9; i++)
    {
        if (b[i] != V9[i]) return 0;
    }
    return 1;
}

int main()
{
    fin >> N;
    for (int i = 1; i <= 9; i++) fin >> V9[i];
    sort (V9 + 1, V9 + 10);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            fin >> V[i][j];
            S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + V[i][j];
        }
    }

    bool w = 1;
    for (int i = 1; i < N - 1 && w; i++)
    {
        for (int j = 1; j < N - 1 && w; j++)
        {
            if (Caut_Binar(S[i][j]))
            {
                l1 = i, c1 = j;
                for (int k = i + 1; k < N && w; k++)
                {
                    if (Caut_Binar(Sum(i+1, 1, k, j)))
                    {
                        l2 = k;
                        for (int k = j + 1; k < N && w; k++)
                        {
                            if (Caut_Binar(Sum(1, j+1, i, k)))
                            {
                                c2 = k;
                                if (Verif())
                                {
                                    sol1 = l1;
                                    sol2 = l2;
                                    sol3 = c1;
                                    sol4 = c2;
                                    w = 0;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    fout << sol1 << ' ' << sol2 << ' ' << sol3 << ' ' << sol4 << '\n';
    fout.close();
    return 0;
}