Cod sursa(job #2070679)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 19 noiembrie 2017 20:15:51
Problema Zone Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <cstdio>
#include <bitset>

using namespace std;
long long s[9],a[513][513];
bitset <9> f;
int verif (long long sum){
    int i;
    for (i=1;i<=9;i++){
        if (s[i]==sum && f[i]==0){
            f[i]=1;
            return 1;
        }
    }
    return 0;
}
int main()
{
    FILE *fin=fopen ("zone.in","r");
    FILE *fout=fopen ("zone.out","w");
    int n,i,j,s1,s2,s3,l1,c1,c2,st,dr,mid;
    long long sum;
    fscanf (fin,"%d",&n);
    for (i=1;i<=9;i++)
        fscanf (fin,"%lld",&s[i]);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            fscanf (fin,"%lld",&a[i][j]);
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    for (s1=1;s1<=9;s1++){
        for (s2=1;s2<=9;s2++){
            for (s3=1;s3<=9;s3++){
                // stiu s1,s2,s3
                //if (s1==2 && s2==3 && s3==6)
                  //  printf ("a");
                if (s1==s2 || s2==s3 || s1==s3)
                    continue;;
                for (i=1;i<n;i++){ // caut L1=i
                    if (a[i][n]!=s[s1]+s[s2]+s[s3])
                        continue;
                    l1=i;
                    st=1;
                    dr=n;
                    while (st<=dr){
                        mid=(st+dr)/2;
                        if (a[l1][mid]==s[s1])
                            break;
                        else if (a[l1][mid]<s[s1])
                            st=mid+1;
                        else dr=mid-1;
                    }
                    if (st>dr)
                        continue; // nu exista niciun C1 posibil pt L1=i si s1
                    c1=mid;
                    // am c1 fixat, acum vreau sa il caut pe c2
                    st=c1+1;
                    dr=n;
                    while (st<=dr){
                        mid=(st+dr)/2;
                        if (a[l1][mid]-a[l1][c1]==s[s2])
                            break;
                        else if (a[l1][mid]-a[l1][c1]<s[s2])
                            st=mid+1;
                        else dr=mid-1;
                    }
                    if (st>dr)
                        continue;
                    c2=mid;
                    // fac un for pt a fixa l2 si verific
                    for (j=i+1;j<=n;j++){
                        f.reset();
                        f[s1]=f[s2]=f[s3]=1;
                        sum=a[j][c1]-a[i][c1];
                        if (verif(sum)==0)
                            continue;
                        sum=a[j][c2]-a[j][c1]-a[i][c2]+a[i][c1];
                        if (verif (sum)==0)
                            continue;
                        sum=a[j][n]-a[i][n]-a[j][c2]+a[i][c2];
                        if (verif (sum)==0)
                            continue;
                        sum=a[n][c1]-a[j][c1];
                        if (verif (sum)==0)
                            continue;
                        sum=a[n][c2]-a[n][c1]-a[j][c2]+a[j][c1];
                        if (verif (sum)==0)
                            continue;
                        fprintf (fout,"%d %d %d %d",l1,j,c1,c2);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}