Cod sursa(job #2197320)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 21 aprilie 2018 18:30:10
Problema Zone Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.18 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int N=512;

int n,v[N+5][N+5];
long long sir[100];
long long s[N+5][N+5];
int r1,c1,r2,c2;
bool viz[100];

long long sum(int r1,int c1,int r2,int c2)
{
    return s[r2][c2]-s[r2][c1-1]-s[r1-1][c2]+s[r1-1][c1-1];
}

int main()
{
    fin>>n;
    for(int i=1;i<=9;i++)
        fin>>sir[i];
    sort(sir+1,sir+9+1);
    for(int i=1;i<=n;i++)
    {
        long long cur=0;
        for(int j=1;j<=n;j++)
        {
            fin>>v[i][j];
            cur+=v[i][j];
            s[i][j]=s[i-1][j]+cur;
        }
    }
    for(r1=1;r1<=n;r1++)
    {
        for(int v1=1;v1<=9;v1++)
        {
            int r=0,pas=(1<<9);
            while(pas)
            {
                if(r+pas<=n && sum(1,1,r1,r+pas)<=sir[v1])
                    r+=pas;
                pas/=2;
            }
            if(sum(1,1,r1,r+pas)==sir[v1])
            {
                viz[v1]=1;
                c1=r;
                for(int v2=1;v2<=9;v2++)
                    if(viz[v2]==0)
                    {
                        r=c1+1;
                        pas=(1<<9);
                        while(pas)
                        {
                            if(r+pas<=n && sum(1,c1+1,r1,r+pas)<=sir[v2])
                                r+=pas;
                            pas/=2;
                        }
                        if(sum(1,c1+1,r1,r)==sir[v2])
                        {
                            viz[v2]=1;
                            c2=r;
                            for(int v3=1;v3<=9;v3++)
                                if(viz[v3]==0)
                                {
                                    r=r1+1;
                                    pas=(1<<9);
                                    while(pas)
                                    {
                                        if(r+pas<=n && sum(r1+1,1,r+pas,c1)<=sir[v3])
                                            r+=pas;
                                        pas/=2;
                                    }
                                    if(sum(r1+1,1,r,c1)==sir[v3])
                                    {
                                        r2=r;
                                        viz[v3]=1;
                                        long long val3,val5,val6,val7,val8,val9;
                                        val3=sum(1,c2+1,r1,n);
                                        val5=sum(r1+1,c1+1,r2,c2);
                                        val6=sum(r1+1,c2+1,r2,n);
                                        val7=sum(r2+1,1,n,c1);
                                        val8=sum(r2+1,c1+1,n,c2);
                                        val9=sum(r2+1,c2+1,n,n);
                                        int g3=0,g5=0,g6=0,g7=0,g8=0,g9=0;
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val3){viz[i]=1;g3=1;}
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val5){viz[i]=1;g5=1;}
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val6){viz[i]=1;g6=1;}
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val7){viz[i]=1;g7=1;}
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val8){viz[i]=1;g8=1;}
                                        for(int i=1;i<=9;i++)if(viz[i]==0 && sir[i]==val9){viz[i]=1;g9=1;}
                                        if(g3*g5*g6*g7*g8*g9==1)
                                        {
                                            fout<<r1<<" "<<r2<<" "<<c1<<" "<<c2;
                                            return 0;
                                        }
                                        memset(viz,0,sizeof(viz));
                                        viz[v1]=viz[v2]=1;
                                    }
                                }
                            viz[v2]=0;
                        }
                    }
                viz[v1]=0;
            }
        }
    }
    return 0;
}
/**

**/