Cod sursa(job #2480700)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 26 octombrie 2019 03:30:48
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <iostream>
#include <fstream>
using namespace std;
#define N 520
int a[N][N],i,j,n,pvm[9],terminat;
long long l[N],c[N],fms[9],s[N][N];
ifstream fin ("zone.in");
ofstream fout ("zone.out");
int bsl (long long x){
    int p = 0;
    for (int it = n; it > 0; it >>= 1)
        while (it + p < n && s[p + it][n - 1] <= x)
        p += it;
    return p;
}
int bsc (long long x){
    int p = 0;
    for (int it = n; it > 0; it >>= 1)
        while (it + p < n && s[n - 1][p + it] <= x)
        p += it;
    return p;
}
bool reusit (){
    int l1,l2,c1,c2;
    if (pvm[0] == 1 && pvm[1] == 2 && pvm[2] == 5 &&
        pvm[6] == 4 && pvm[4] == 3 && pvm[5] == 8){
        l1 = 0;
    }
    l1 = bsl (fms[pvm[0]] + fms[pvm[1]] + fms[pvm[2]]);
    l2 = bsl (fms[pvm[0]] + fms[pvm[1]] + fms[pvm[2]] + fms[pvm[3]] + fms[pvm[4]] + fms[pvm[5]]);
    c1 = bsc (fms[pvm[0]] + fms[pvm[3]] + fms[pvm[6]]);
    c2 = bsc (fms[pvm[0]] + fms[pvm[3]] + fms[pvm[6]] + fms[pvm[1]] + fms[pvm[4]] + fms[pvm[8]]);
    if (fms[pvm[0]] == s[l1][c1] &&
        fms[pvm[3]] == s[l2][c1] - s[l1][c1] &&
        fms[pvm[6]] == s[n - 1][c1] - s[l2][c1] &&
        fms[pvm[1]] == s[l1][c2] - s[l1][c1] &&
        fms[pvm[2]] == s[l1][n - 1] - s[l1][c2] &&
        fms[pvm[4]] == s[l2][c2] - s[l1][c2] - s[l2][c1] + s[l1][c1] &&
        fms[pvm[5]] == s[l2][n - 1] - s[l2][c2] - s[l1][n - 1] + s[l1][c2] &&
        fms[pvm[7]] == s[n - 1][c2] - s[l2][c2] - s[n - 1][c1] + s[l2][c1] &&
        fms[pvm[8]] == s[n - 1][n - 1] - s[n - 1][c2] - s[l2][n - 1] + s[l2][c2]){
        fout << l1 + 1<< " " << l2 + 1<< " " << c1 + 1<< " " << c2 + 1;
        return 1;
    }
    return 0;
}
void bkt (int k,int mask){
    if (terminat)
        return;
    if (mask + 1 == (1 << 9)){
        if (reusit ())
            terminat = 1;
    }
    for (int i = 0; i < 9 && !terminat; ++i)
        if (mask & (1 << i))
            continue;
        else{
            pvm[k] = i;
            bkt(k + 1, mask + (1 << i));
            pvm[k] = 0;
        }
}
int main()
{
    fin >> n;
    for (i = 0; i < 9; ++i)
        fin >> fms[i];
    for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j){
        fin >> a[i][j];
        l[i] += a[i][j];
        c[j] += a[i][j];
        if (i > 0 && j > 0)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        else{
            if (i + j < 1)
                s[i][j] = a[i][j];
            if (i > 0)
                s[i][j] = a[i][j] + s[i - 1][j];
            if (j > 0)
                s[i][j] = a[i][j] + s[i][j - 1];
        }
    }
    for (i = 0; i <= n; ++i){
        s[i][n] = s[i][n - 1] + 1;
        s[n][i] = s[n - 1][i] + 1;
    }
    bkt (0,0);
/*    l1 = bsl (fms[0] + fms[1] + fms[2]);
    l2 = bsl (fms[0] + fms[1] + fms[2] + fms[3] + fms[4] + fms[5]);
    c1 = bsc (fms[0] + fms[3] + fms[6]);
    c2 = bsc (fms[0] + fms[3] + fms[6] + fms[1] + fms[4] + fms[8]);
*/

    //fout << l1 << " " << l2 << " " << c1 << " " << c2;
    return 0;
}