Cod sursa(job #1909232)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 7 martie 2017 11:58:22
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <fstream>
#define DIM 515
using namespace std;

ifstream fin ("zone.in");
ofstream fout ("zone.out");
int n,i,j,v[10],a[DIM][DIM],s[DIM][DIM],x[10],OK;
int nr,nr2,nr3,nr4,nr5,nr6,p,u,pr,ul,mid,st,dr,mij,m;
int cont (int pas){
    for (int i=1;i<pas;i++)
        if (x[i] == x[pas])
            return 0;
    return 1;

}
void back (int pas){

    if (pas > 9){
        // fixam linia l1
        for (int i=1;i<n;i++){
            // cautam binar coloana c1
            p = 1;
            u = n-1;
            while (p<=u){
                m = (p+u)/2;
                nr = s[i][m];
                if (nr == v[x[1]])
                    break;
                else
                    if (nr < v[x[1]])
                        p = m+1;
                    else
                        u = m-1;
            }
            if (p<=u){ // am putut fixa coloana 1 (m)
                // cautam binar coloana 2;
                st = m+1;
                dr = n;
                while (st <= dr){
                    mid = (st+dr)/2;
                    nr = s[i][mid]-s[i][m];
                    nr2 = s[i][n] - s[i][mid];
                    if (nr == v[x[2]] && nr2 == v[x[3]])
                        break;
                    else
                        if (nr < v[x[2]])
                            st = mid+1;
                        else
                            dr = mid-1;
                }

                if (st <= dr){ // am putut fixa coloana 2 (mid)
                    // cautam binar linia 2
                    pr = 2;
                    ul = n;
                    while (pr<=ul){
                        mij = (pr+ul)/2;
                        nr = s[mij][m] - s[i][m];
                        nr2 = s[mij][mid]-s[mij][m]-s[i][mid]+s[i][m];
                        nr3 = s[mij][n]-s[mij][mid]-s[i][n]+s[i][mid];
                        nr4 = s[n][m]-s[mij][m];
                        nr5 = s[n][mid]-s[n][m]-s[mij][mid]+s[mij][m];
                        nr6 = s[n][n]-s[n][mid]-s[mij][n]+s[mij][mid];
                        if (nr==v[x[4]]&&nr2==v[x[5]]&&nr3==v[x[6]]&&nr4==v[x[7]]&&nr5==v[x[8]]&&nr6==v[x[9]])
                            break;
                        else
                            if (nr < v[x[4]])
                                pr = mij+1;
                            else
                                ul = mij-1;
                    }
                    if (pr <= ul){
                        // am putut fixa si linia a doua
                        // deci am gasit solutia
                        fout<<i<<" "<<mij<<" "<<m<<" "<<mid;
                        OK = 1;
                        break;
                        //continue;
                       // return 0;
                    }
                }

            }
        }
        return;
    }
    if (OK==0){
        for (int i=1;i<=9;i++){
            x[pas] = i;
            if (cont(pas))
                back (pas+1);
        }
    }

}
int main (){

    fin>>n;
    for (i=1;i<=9;i++)
        fin>>v[i]; // sumele
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            fin>>a[i][j];
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    back (1);

    return 0;
}