Cod sursa(job #2078357)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 29 noiembrie 2017 13:55:40
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.88 kb
#include <fstream>
#include <bitset>
#define DIM 515
#define INF 2000000000
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;
long long minl1 = INF,minl2 = INF,minc1 = INF,minc2 = INF,L1,L2,C1,C2;
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 cmp (long long l1,long long l2,long long c1,long long c2){
    if (l1 < minl1){
        minl1 = l1;
        L1 = l1;
        L2 = l2;
        C1 = c1;
        C2 = c2;
    }
    else{
        if (l1 == minl1){
            if (c1 < minc1){
                minc1 = c1;
                L1 = l1;
                L2 = l2;
                C1 = c1;
                C2 = c2;
            }
            else{
                if (c1 == minc1){
                    if (l2 < minl2){
                        minl2 = l2;
                        L1 = l1;
                        L2 = l2;
                        C1 = c1;
                        C2 = c2;
                    }
                    else{
                        if (l2 == minl2){
                            if (c2 < minc2){
                                minc2 = c2;
                                L1 = l1;
                                L2 = l2;
                                C1 = c1;
                                C2 = c2;
                            }
                        }
                    }
                }
            }
        }
    }
}
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;
                        cmp(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;
                   // }




                }
            }
        }
    }
    fout<<L1<<" "<<L2<<" "<<C1<<" "<<C2;
    return 0;
}