Cod sursa(job #3238667)

Utilizator Victor5539Tanase Victor Victor5539 Data 28 iulie 2024 17:45:59
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.71 kb
#include <fstream>
#include <unordered_map>
#include <algorithm>

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

long long s[515][515],i,j,ln1,ln2,c1,c2,n,v[15],st,dr,mij;
unordered_map <long long,long long> m;

long long suma(long long x1,long long y1,long long x2,long long y2)
{
    return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n;
    for (i=1; i<=9; i++)
    {fin>>v[i]; m[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][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }

    for (ln1=1; ln1<=n-2; ln1++)
        for (c1=1; c1<=n-2; c1++)
        if (m[s[ln1][c1]]!=0)
        {
            m[s[ln1][c1]]--;
            for (i=1; i<=9; i++)
                if (m[v[i]])
                {
                    st=ln1+1; dr=n-1;
                    while (st<=dr)
                    {
                        mij=(st+dr)>>1;
                        if (s[mij][c1]-s[ln1][c1]<v[i])
                            st=mij+1;
                        else
                        if (s[mij][c1]-s[ln1][c1]>v[i])
                            dr=mij-1;
                        else
                        break;
                    }

                    if (s[mij][c1]-s[ln1][c1]==v[i])
                    {
                        ln2=mij; m[v[i]]--;
                        if (m[s[n][c1]-s[ln2][c1]])
                        {
                            m[s[n][c1]-s[ln2][c1]]--;

                            for (j=1; j<=9; j++)
                                if (m[v[j]])
                                {
                                    st=c1+1; dr=n-1;
                                    while (st<=dr)
                                    {
                                        mij=(st+dr)>>1;
                                        if (s[ln1][mij]-s[ln1][c1]<v[j])
                                            st=mij+1;
                                        else
                                        if (s[ln1][mij]-s[ln1][c1]>v[j])
                                            dr=mij-1;
                                        else
                                        break;
                                    }

                                    if (s[ln1][mij]-s[ln1][c1]==v[j])
                                    {
                                        c2=mij; m[v[j]]--;
                                        if (m[suma(ln1+1,c1+1,ln2,c2)])
                                            {
                                                m[suma(ln1+1,c1+1,ln2,c2)]--;
                                                if (m[suma(ln2+1,c1+1,n,c2)])
                                                    {
                                                        m[suma(ln2+1,c1+1,n,c2)]--;
                                                        if (m[s[ln1][n]-s[ln1][c2]])
                                                        {
                                                            m[s[ln1][n]-s[ln1][c2]]--;
                                                            if (m[suma(ln1+1,c2+1,ln2,n)])
                                                            {
                                                                m[suma(ln1+1,c2+1,ln2,n)]--;
                                                                if (suma(ln2+1,c2+1,n,n))
                                                                {
                                                                    fout<<ln1<<" "<<ln2<<" "<<c1<<" "<<c2;
                                                                    return 0;
                                                                }
                                                                m[suma(ln1+1,c2+1,ln2,n)]++;
                                                            }
                                                            m[s[ln1][n]-s[ln1][c2]]++;
                                                        }
                                                        m[suma(ln2+1,c1+1,n,c2)]++;
                                                    }
                                                m[suma(ln1+1,c1+1,ln2,c2)]++;
                                            }
                                        m[v[j]]++;
                                    }
                                }



                            m[s[n][c1]-s[ln2][c1]]++;
                        }
                        m[v[i]]++;
                    }
                }

            m[s[ln1][c1]]++;
        }
    return 0;
}