Cod sursa(job #1636531)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 7 martie 2016 10:36:30
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define DIM 515

long long Suma[15], Mat[DIM][DIM];
int N;

int Try(int l1, int l2, int c1, int c2);
int bin_search(long long x);

int main() {
    freopen("zone.in","r",stdin);
    freopen("zone.out","w",stdout);

    scanf("%d\n", &N);

    for(int i = 1; i <= 9; ++i) {
        scanf("%lld", &Suma[i]);
    }

    sort(Suma + 1, Suma + 10);

    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            scanf("%d", &Mat[i][j]);
            Mat[i][j] += 1LL * Mat[i - 1][j] + Mat[i][j - 1] - Mat[i - 1][j - 1];
        }
    }

    for(int l1 = 1; l1 < N; ++l1) {
        for(int c1 = 1; c1 < N; ++c1) {
            int p = bin_search(Mat[l1][c1]);

            if(Suma[p] == Mat[l1][c1]) {
                for(int l2 = l1 + 1; l2 <= N; ++l2) {
                    for(int c2 = c1 + 1; c2 <= N; ++c2) {
                        if(Try(l1, l2, c1, c2) == 1) {
                            cout << l1 << ' ' << l2 << ' ' << c1 << ' ' << c2 << '\n';
                            return 0;
                        }
                    }
                }
            }
        }
    }

    cout << "N-aveti solutie :'(\n";

    return 0;
}

int Try(int l1, int l2, int c1, int c2) {
    long long VS[14];

    VS[1] = Mat[l1][c1];
    VS[2] = Mat[l1][c2] - VS[1];
    VS[3] = Mat[l1][N] - VS[2] - VS[1];

    VS[4] = Mat[l2][c1] - VS[1];
    VS[5] = Mat[l2][c2] - VS[2] - VS[4] - VS[1];
    VS[6] = Mat[l2][N] - VS[1] - VS[2] - VS[3] - VS[4] - VS[5];

    VS[7] = Mat[N][c1] - VS[4] - VS[1];
    VS[8] = Mat[N][c2] - VS[1] - VS[2] - VS[4] - VS[5] - VS[7];
    VS[9] = Mat[N][N] - VS[1] - VS[2] - VS[3] - VS[4] - VS[5] - VS[6] - VS[7] - VS[8];

    sort(VS + 1, VS + 10);

    for(int i = 1; i < 10; ++i) {
        if(VS[i] != Suma[i]) {
            return 0;
        }
    }

    return 1;
}

int bin_search(long long x) {
    int put = 8;
    int pos = 0;

    while(put) {
        if(pos + put <= 9) {
            if(Suma[pos + put] <= x) {
                pos += put;
            }
        }

        put >>= 1;
    }

    return pos;
}