Cod sursa(job #2135459)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 18 februarie 2018 20:58:54
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include<fstream>
using namespace std;
ifstream in ("zone.in");
ofstream out ("zone.out");
int s[513][513],iesi, mat[513][513],v[10],n,hz[10],f[10];
int sum (int a, int b, int c, int d) {
    return s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1];
}
int cauta_binar (int point,int st, int dr,int ax) {
    int x0 = st;
    while (st <= dr) {
        int mid = (st + dr) >> 1;
        if (sum (1,x0,point, mid ) <= v[ax] ) {
            st = mid + 1;
        }
        else {
            dr = mid - 1;
        }
    }
    return dr;
}
void back (int p) {
    if (iesi == 1) {
        return;
    }
    if (p >= 10) {
        for (int a = 1; a < n; a ++) {
            for (int b = a + 1; b <= n; b ++) {
                int c = cauta_binar (a,1,n-1,1);
                if (sum (1,1,a,c) == v[1] &&
                    sum (a+1,1,b,c) == v[4] &&
                    sum (b+1,1,n,c) == v[7]) {
                    int d = cauta_binar (a,c+1,n,2);
                    if (sum (1,c+1,a,d) == v[2] &&
                        sum (a+1,c+1,b,d) == v[5] &&
                        sum (b+1,c+1,n,d) == v[8] &&
                        sum (1,d+1,a,n) == v[3] &&
                        sum (a+1,d+1,b,n) == v[6] &&
                        sum (b+1,d+1,n,n) == v[9]
                        )  {
                        out << a <<" "<< b <<" "<< c <<" "<< d;
                        iesi = 1;
                        return;
                    }
                }
            }
        }
    }
    else {
        for (int i = 1; i <= 9; i ++) {
            if (hz[i] == 0) {
                hz[i] = 1;
                v[p] = f[i];
                back (p+1);
                hz[i] = 0;
                if (iesi == 1) {
                    return;
                }
            }
        }
    }
}
int main (void) {
    in >> n;
    for (int i = 1; i <= 9; i ++) {
        in >> f[i];
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            in >> mat[i][j];
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i][j];
        }
    }
    back (1);

    return 0;
}