Cod sursa(job #1401899)

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

using namespace std;
typedef int64_t var;

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

int n;

#define MAXN 1024

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

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

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

bool cmp(const Sol &a, const 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;
}


Sol best(200000, 200000, 200000, 200000);

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];



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

    Sol pret(l1, l2-1, c1, c2-1);
    if(l1*l2*c1*c2 && cmp(pret, best)) {
        best = pret;
    }

}



int main() {

    fin>>n;
    var v;

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


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

        }
    }

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

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

    for(int 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()));

    auto &sol = best;
    fout<<sol.l1<<" "<<sol.l2<<" "<<sol.c1<<" "<<sol.c2<<'\n';

    return 0;
}