Cod sursa(job #1401869)

Utilizator retrogradLucian Bicsi retrograd Data 26 martie 2015 10:29:38
Problema Zone Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include<fstream>
#include<algorithm>
#include<tuple>

using namespace std;
typedef int64_t var;

ifstream fin("zone.in");
ofstream fout("zone.out");

var n;

#define MAXN 600

struct Sol {
    var l1, c1, l2, c2;
    Sol(var a, var b, var c, var d) {
        l1 = a;
        l2 = b;
        c1 = c;
        c2 = d;
    }
};
vector<Sol> SOL;
var LIN[MAXN], COL[MAXN];
var LINB[MAXN], COLB[MAXN];
var A[MAXN][MAXN];
vector<var> VAL(9);
var M;

var bs(var val, var *V) {
    var poz = 0;
    for(var i=M; i; i>>=1) {
        if(poz+i <= n && V[poz+i] <= val)
            poz += i;
    }
    if(V[poz] == val)
        return poz;
    return 0;
}

var bs2(var val, var *V) {
    var poz = 0;
    for(var i=M; i; i>>=1) {
        if(poz+i<=n && V[poz+i] >= val)
            poz+=i;
    }
    if(V[poz] == val)
        return poz;
    return 0;
}

var L[3], C[3];
void check() {
    L[0] = VAL[0] + VAL[1] + VAL[2];
    L[1] = VAL[3] + VAL[4] + VAL[5];
    L[2] = VAL[6] + VAL[7] + VAL[8];

    C[0] = VAL[0] + VAL[3] + VAL[6];
    C[1] = VAL[1] + VAL[4] + VAL[7];
    C[2] = VAL[2] + VAL[5] + VAL[8];



    var l1 = bs(L[0], LIN);
    var l2 = bs2(L[2], LINB);
    var c1 = bs(C[0], COL);
    var c2 = bs2(C[2], COLB);

    if(l1*l2*c1*c2) {
        SOL.push_back(Sol(l1, l2-1, c1, c2-1));
    }

}



int main() {

    fin>>n;
    var v;

    for(var i=1; i<=9; i++) {
        fin>>v;
        VAL[i-1] = v;
    }


    for(var i=1; i<=n; i++) {
        for(var j=1; j<=n; j++) {
            fin>>A[i][j];
            LIN[i] += A[i][j];
            COL[j] += A[i][j];

        }
    }

    for(var i=1; i<=n; i++) {
        LINB[i] = LIN[i];
        COLB[i] = COL[i];
    }

    for(var i=1; i<=n; i++) {
        LIN[i] += LIN[i-1];
        COL[i] += COL[i-1];
    }

    for(var i=n-1; i>=1; i--) {
        LINB[i] += LINB[i+1];
        COLB[i] += COLB[i+1];
    }

    for(M=1; M<=n; M<<=1);
    M>>=1;

    sort(VAL.begin(), VAL.end());

    do {
        check();
    } while(next_permutation(VAL.begin(), VAL.end()));

    sort(SOL.begin(), SOL.end(), [](Sol a, Sol b) {
            if(a.l1 < b.l1) return 1;
            if(a.l1 > b.l1) return 0;

            if(a.c1 < b.c1) return 1;
            if(a.c1 > b.c1) return 0;

            if(a.l2 < b.l2) return 1;
            if(a.l2 > b.l2) return 0;

            if(a.c2 < b.c2) return 1;
            if(a.c2 > b.c2) return 0;

            return 0;

         });

    auto sol = SOL[0];
    fout<<sol.l1<<" "<<sol.l2<<" "<<sol.c1<<" "<<sol.c2<<'\n';

    return 0;
}