Cod sursa(job #2078077)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 28 noiembrie 2017 21:26:22
Problema Zone Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <fstream>
#define DIM 515
using namespace std;

ifstream fin ("zone.in");
ofstream fout ("zone.out");
int n,i,j,a[DIM][DIM],s[DIM][DIM],v[11],x[11],OK;
int verif (int pas){
    for (int i=1;i<pas;i++)
        if (x[i] == x[pas])
            return 0;
    return 1;
}
void back (int pas){
    if (OK == 1)
        return;
    if (pas == 10){
        /// fixam prima linie
        int c1,c2,l1,l2,mid,st,dr;
        for (int i=1;i<n-1;i++){
            /// cautam binar coloana 1
            int ok = 0;
            st = 1;
            dr = n-2;
            while (st <= dr){
                mid = (st+dr)/2;
                if (s[i][mid] == v[x[1]]){
                    c1 = mid;
                    break;
                }
                else{
                    if (s[i][mid] < v[x[1]])
                        st = mid+1;
                    else
                        dr = mid-1;
                }
            }
            if (st > dr){ /// nu am putut fixa coloana 1
                ok = 1;
                continue;
            }
            //if (st <= dr){/// inseamna ca am gasit suma 1
           // int c1 = mid;
            /// cautam binar coloana 2
            st = c1+1;
            dr = n-1;
            while (st <=dr){
                mid = (st+dr)/2;
                if (s[i][mid] - s[i][c1] == v[x[2]])
                    break;
                else
                    if (s[i][mid] - s[i][c1] < v[x[2]])
                        st = mid+1;
                    else
                        dr = mid-1;
            }
            if (st > dr){
                ok = 1;
                continue;
            }
            else{
                if (s[i][n] - s[i][mid] == v[x[3]]){
                    /// am putut fixa coloana a doua
                    c2 = mid;
                }
                else{
                    ok = 1;
                    continue;
                }
            }

            /// cautam binar linia a doua
            st = i+1;
            dr = n-1;
            while (st <= dr){
                mid = (st+dr)/2;
                int sum = s[mid][c1] - s[i][c1];
                if (sum == v[x[4]]){
                    l2 = mid;
                    break;
                }
                else{
                    if (sum < v[x[4]])
                        st = mid+1;
                    else
                        dr = mid-1;
                }
            }
            if (st > dr){ /// nu am putut fixa linia 2
                ok = 1;
                continue;
            }
            //int l2 = mid;
            int sum5 = s[mid][c2] - s[mid][c1] - s[i][c2] + s[i][c1];
            int sum6 = s[mid][n] - s[mid][c2] - s[i][n] + s[i][c2];
            int sum7 = s[n][c1] - s[l2][c1];
            int sum8 = s[n][c2] - s[n][c1] - s[l2][c2] + s[l2][c1];
            int sum9 = s[n][n] - s[n][c2] - s[l2][n] + s[l2][c2];
            if (!(sum5 == v[x[5]] && sum6 == v[x[6]] && sum7 == v[x[7]] && sum8 == v[x[8]] && sum9 == v[x[9]]) ){
                ok = 1;
                continue;
            }

            /// am gasit o solutie;

            fout<<i<<" "<<l2<<" "<<c1<<" "<<c2;
            OK = 1;
            return;
        }


    }
    for (int i=1;i<=9;i++){
        x[pas] = i;
        if (verif(pas))
            back (pas+1);
    }
}

int main (){

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


    return 0;
}