Cod sursa(job #2135465)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 18 februarie 2018 21:03:45
Problema Zone Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include<fstream>
using namespace std;
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
} in ("zone.in");
ofstream out ("zone.out");
long long iesi, mat[513][513],n,hz[10];
long long s[513][513],f[10],v[10];
long long 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;
}