Cod sursa(job #2072066)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 21 noiembrie 2017 12:55:11
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <cstdio>
#include <bitset>

using namespace std;
long long s[10],a[513][513];
bitset <10> 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,l2;
    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++){
        // stiu s1
        for (i=1;i<n;i++){ // caut L1=i
            if (s1==2 && i==1)
                printf ("a");
            l1=i;
            st=1;
            dr=n;
            while (st<=dr){
                mid=(st+dr)/2;
                if (a[l1][mid]<s[s1])
                    st=mid+1;
                else dr=mid-1;
            }
            if (a[l1][st]!=s[s1])
                continue; // nu exista niciun C1 posibil pt L1=i si s1
            c1=st;
            // am c1 fixat
            for (s2=1;s2<=9;s2++){
                if (s1==s2)
                    continue;
                // caut binar c2 pt s2 ul curent
                st=c1+1;
                dr=n;
                while (st<=dr){
                    mid=(st+dr)/2;
                    if (a[l1][mid]-a[l1][c1]<s[s2])
                        st=mid+1;
                    else dr=mid-1;
                }
                if (a[l1][st]-a[l1][c1]!=s[s2])
                    continue;
                c2=st;
                // mai fixez un s3 si caut binar l2
                for (s3=1;s3<=9;s3++){
                    if (s3==s1 || s3==s2)
                        continue;
                    st=i+1;
                    dr=n;
                    while (st<=dr){
                        mid=(st+dr)/2;
                        if (a[mid][c1]-a[l1][c1]<s[s3])
                            st=mid+1;
                        else dr=mid-1;
                    }
                    if (a[st][c1]-a[l1][c1]!=s[s3])
                        continue;
                    l2=st; // am practic fixate l1 l2 c1 si c2, verific daca sunt solutii
                    f.reset();
                    f[s1]=f[s2]=f[s3]=1;
                    sum=a[i][n]-a[i][c2];
                    if (verif(sum)==0)
                        continue;
                    sum=a[l2][c2]-a[l2][c1]-a[i][c2]+a[i][c1];
                    if (verif (sum)==0)
                        continue;
                    sum=a[l2][n]-a[i][n]-a[l2][c2]+a[i][c2];
                    if (verif (sum)==0)
                        continue;
                    sum=a[n][c1]-a[l2][c1];
                    if (verif (sum)==0)
                        continue;
                    sum=a[n][n]-a[n][c2]-a[l2][n]+a[l2][c2];
                    if (verif (sum)==0)
                        continue;
                    fprintf (fout,"%d %d %d %d",i,l2,c1,c2);
                    return 0;
                }
            }
        }
    }
    return 0;
}