Cod sursa(job #2357488)

Utilizator anamariatoaderAna Toader anamariatoader Data 27 februarie 2019 14:29:00
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <fstream>
#include <algorithm>

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

int n,i,j,k,q,v[10],l1,l2,c1,c2;
long long s[515][515];
bool f[10];

int C1(int S){
    int st=1,dr=n-2,mij,sol=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(s[l1][mij]==S){
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return sol;
}

int C2(int S){
    int st=c1+1,dr=n-2,mij,sol=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(s[l1][mij]-s[l1][c1]==S){
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return sol;
}

int L2(int S){
    int st=l1+1,dr=n-1,mij,sol=0;
    while(st<=dr){
        mij=(st+dr)/2;
        if(s[mij][c1]-s[mij-1][c1]==S){
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return sol;
}

bool valid(){
    ///VERIFIC S5
    int s5 = s[l2][c2]-s[l2][c1]-s[l1][c2]+s[l1][c1];
    int poz5 = 0;
    for(int i=1;i<=9 && !poz5;i++)
        if(f[i]==0 && v[i]==s5){
            poz5=i;
            f[i]=1;
        }
    if(!poz5){
        f[poz5]=0;
        return 0;
    }

    ///VERIFIC S6
    int s6 = s[l2][n]-s[l2][c2]-s[l1][n]+s[l1][c2];
    int poz6 = 0;
    for(int i=1;i<=9 && !poz6;i++)
        if(f[i]==0 && v[i]==s6){
            poz6=i;
            f[i]=1;
        }
    if(!poz6){
        f[poz5]=f[poz6]=0;
        return 0;
    }

    ///VERIFIC S7
    int s7 = s[n][c1]-s[l2][c1];
    int poz7 = 0;
    for(int i=1;i<=9 && !poz7;i++)
        if(f[i]==0 && v[i]==s7){
            poz7=i;
            f[i]=1;
        }
    if(!poz7){
        f[poz5]=f[poz6]=f[poz7]=0;
        return 0;
    }

    ///VERIFIC S8
    int s8 = s[n][c2]-s[n][c1]-s[l2][c2]+s[l2][c1];
    int poz8 = 0;
    for(int i=1;i<=9 && !poz8;i++)
        if(f[i]==0 && v[i]==s8){
           poz8=i;
           f[i]=1;
        }
    if(!poz8){
        f[poz5]=f[poz6]=f[poz7]=f[poz8]=0;
        return 0;
    }

    ///VERIFIC S9
    int s9 = s[n][n]-s[n][c2]-s[l2][n]+s[l2][c2];
    int poz9 = 0;
    for(int i=1;i<=9 && !poz9;i++)
        if(f[i]==0 && v[i]==s9){
            poz9=i;
            f[i]=1;
        }
    if(!poz9){
        f[poz5]=f[poz6]=f[poz7]=f[poz8]=f[poz9]=0;
        return 0;
    }
    return 1;
}

int main(){
    fin>>n;
    for(i=1;i<=9;i++)
        fin>>v[i];
    sort(v+1,v+10);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++){
         fin>>s[i][j];
         s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
      }
    for(l1=1;l1<n-1;l1++){
      for(i=1;i<=9;i++){
         c1=0;
         if(C1(v[i])!=0){ // fixez C1
            c1=C1(v[i]);
            f[i]=1;
            /// CAUT C2
            for(j=1;j<=9;j++)
                if(!f[j] && C2(v[j])!=0){
                    c2=C2(v[j]);
                    f[j]=1;
                    /// CAUT L2
                    for(k=1;k<=9;k++)
                        if(!f[k] && L2(v[k])!=0){
                            l2=L2(v[k]);
                            f[k]=1;
                            ///Verific daca este buna configuratia
                            if(valid()){
                                fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
                            }

                        }
                    f[j]=0;
                }
            f[i]=0;
         }
      }
    }
    return 0;
}