Cod sursa(job #2078345)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 29 noiembrie 2017 13:40:19
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.58 kb
#include <fstream>
#include <bitset>
#define DIM 515
using namespace std;

ifstream fin ("zone.in");
ofstream fout ("zone.out");
long long n,i,j,a[DIM][DIM],s[DIM][DIM],v[11],x[11],OK,s1,s2,s3;
bitset <10> f;
long long verif (long long sum){
    for (long long i=1;i<=9;i++){
        if (v[i] == sum && f[i] == 0){
            f[i] = 1;
            return 1;
        }
    }
    return 0;

}
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);
    long long c1,c2,l1,l2,mid,st,dr;
    ///
    for (s1=1;s1<=9;s1++){
        for (long long i=1;i<n-1;i++){
            /// cautam binar coloana 1
            long long ok = 0;
            st = 1;
            dr = n-2;
            while (st <= dr){
                mid = (st+dr)/2;
                if (s[i][mid] == v[s1]){
                    c1 = mid;
                    break;
                }
                else{
                    if (s[i][mid] < v[s1])
                        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
           // long long c1 = mid;
            /// cautam binar coloana 2
            for (s2=1;s2<=9;s2++){
                if (s1 == s2)
                    continue;
                st = c1+1;
                dr = n-1;
                while (st <=dr){
                    mid = (st+dr)/2;
                    if (s[i][mid] - s[i][c1] == v[s2])
                        break;
                    else
                        if (s[i][mid] - s[i][c1] < v[s2])
                            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;
                    }
                }*/
                c2 = mid;
                for (s3=1;s3<=9;s3++){ /// fixam suma a treia
                    if (s2 == s3 || s1 == s3)
                        continue;
                    /// cautam binar linia a doua
                    st = i+1;
                    dr = n-1;
                    while (st <= dr){
                        mid = (st+dr)/2;
                        long long sum = s[mid][c1] - s[i][c1];
                        if (sum == v[s3]){
                            l2 = mid;
                            break;
                        }
                        else{
                            if (sum < v[s3])
                                st = mid+1;
                            else
                                dr = mid-1;
                        }
                    }
                    if (st > dr){ /// nu am putut fixa linia 2
                        ok = 1;
                        continue;
                    }
                    //long long l2 = mid;
                    long long sum3 = s[i][n] - s[i][c2];
                    long long sum5 = s[mid][c2] - s[mid][c1] - s[i][c2] + s[i][c1];
                    long long sum6 = s[mid][n] - s[mid][c2] - s[i][n] + s[i][c2];
                    long long sum7 = s[n][c1] - s[l2][c1];
                    long long sum8 = s[n][c2] - s[n][c1] - s[l2][c2] + s[l2][c1];
                    long long sum9 = s[n][n] - s[n][c2] - s[l2][n] + s[l2][c2];
                    f.reset();
                    f[s1] = f[s2] = f[s3] = 1;
                    if (verif(sum3) && verif (sum5) && verif (sum6) && verif (sum7) && verif(sum8) && verif (sum9)){
                        /// am gasit o solutie;
                        fout<<i<<" "<<l2<<" "<<c1<<" "<<c2;
                        return 0;
                    }

                 //   if (!(sum5 == v[x[5]] && sum6 == v[x[6]] && sum7 == v[x[7]] && sum8 == v[x[8]] && sum9 == v[x[9]]) ){
                  //      ok = 1;
                   //     continue;
                   // }




                }
            }
        }
    }

    return 0;
}