Cod sursa(job #2357944)

Utilizator mihaimodiMihai Modi mihaimodi Data 27 februarie 2019 20:20:46
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.49 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
int a[515][515];
int s[10];
bool viz[10];
int x,n;
int cautbin_lin(int l1, int c1, int l2, int c2, int val)
{
    int st=l1,dr=l2;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        int x=a[mid][c2]+a[l1-1][c1-1]-a[mid][c1-1]-a[l1-1][c2];
        if(x==val)
            return mid;
        else if(x>val)
            dr=mid-1;
        else if(x<val)
            st=mid+1;
    }
    return -1;
}
int cautbin_col(int l1, int c1, int l2, int c2, int val)
{
    int st=c1,dr=c2;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        int x=a[l2][mid]+a[l1-1][c1-1]-a[l2][c1-1]-a[l1-1][mid];
        if(x==val)
            return mid;
        else if(x>val)
            dr=mid-1;
        else if(x<val)
            st=mid+1;
    }
    return -1;
}
int main()
{
    fin>>n;
    for(int i=1;i<=9;i++)
        fin>>s[i];
    sort(s+1,s+10);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            fin>>x;
            a[i][j]=x+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }

    for(int l1=1;l1<=n-2;l1++)
        for(int s1=1;s1<=9;s1++)
            if(!viz[s1])
            {
                int c1=cautbin_col(1,1,l1,n-2,s[s1]);
                viz[s1]=1;
                for(int s2=1;s2<=9;s2++)
                    if(!viz[s2])
                    {
                        int c2=cautbin_col(1,c1+1,l1,n-1,s[s2]);
                        if(c2!=-1)
                        {
                            viz[s2]=1;
                            int sum3=a[l1][n]+a[0][c2-1]-a[l1][c2-1]-a[0][n];
                            for(int s3=1;s3<=9;s3++)
                            {
                                if(!viz[s3]&&s[s3]==sum3)
                                {
                                    viz[s3]=1;
                                    for(int s4=1;s4<=9;s4++)
                                        if(!viz[s4])
                                        {
                                            int l2=cautbin_lin(l1+1,1,n-1,c1,s[s4]);
                                            if(l2!=-1)
                                            {
                                                viz[s4]=1;
                                                int sum5=a[l2][c2]+a[l1-1][c1-1]-a[l2][c1-1]-a[l1-1][c2];
                                                for(int s5=1;s5<=9;s5++)
                                                {
                                                    if(!viz[s5]&&s[s5]==sum5)
                                                    {
                                                        viz[s5]=1;
                                                        int sum6=a[l2][n]+a[l1-1][c2-1]-a[l2][c2-1]-a[l2-1][n];
                                                        for(int s6=1;s6<=9;s6++)
                                                        {
                                                            if(!viz[s6]&&s[s6]==sum6)
                                                            {
                                                                viz[s6]=1;
                                                                int sum7=a[n][c1]+a[l2-1][0]-a[n][0]-a[l2-1][c1];
                                                                for(int s7=1;s7<=9;s7++)
                                                                {
                                                                    if(!viz[s7]&&s[s7]==sum7)
                                                                    {
                                                                        viz[s7]=1;
                                                                        int sum8=a[n][c2]+a[l2-1][c2-1]-a[n][c1-1]-a[l2-1][c2];
                                                                        for(int s8=1;s8<=9;s8++)
                                                                        {
                                                                            if(!viz[s8]&&s[s8]==sum8)
                                                                            {
                                                                                fout<<l1<<' '<<l2<<' '<<c1<<' '<<c2;
                                                                                return 0;
                                                                            }
                                                                        }
                                                                        viz[s7]=0;
                                                                    }
                                                                }
                                                                viz[s6]=0;
                                                            }
                                                        }
                                                        viz[s5]=0;
                                                    }
                                                }
                                                viz[s4]=0;
                                            }
                                        }
                                    viz[s3]=0;
                                }
                            }
                        }
                        viz[s2]=0;
                    }
                viz[s1]=0;
            }

    return 0;
}