Cod sursa(job #3254777)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 8 noiembrie 2024 19:59:09
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.59 kb
#include <fstream>
#include <map>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
map <long long, long long> m1, m2;
int v[513][513], w[10];
int main()
{
    int n, l1, l2, c1, c2, st, dr, mid;
    fin >> n;
    for(int i=1; i<=9; i++)
    {
        fin >> w[i];
        m1[w[i]]++;
        m2[w[i]]++;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            fin >> v[i][j];
            v[i][j]+=(v[i-1][j]+v[i][j-1]-v[i-1][j-1]);
        }
    }
    for(int i=1; i<=n-2; i++)
    {
        for(int q=1; q<=9; q++)
        {
            st=1, dr=n, mid;
            while(st<=dr)
            {
                mid=(st+dr)/2;
                if(v[i][mid]==w[q])
                    break;
                else if(v[i][mid]>w[q])
                    dr = mid-1;
                else
                    st = mid+1;
            }
            if(st<=dr)
            {
                l1=i;
                c1=mid;
                m1[v[l1][c1]]--;
                for(int q=1; q<=9; q++)
                {
                    if(m1[w[q]])
                    {
                        st=l1+1; dr=n;
                        while(st<=dr)
                        {
                            mid = (st+dr)/2;
                            if(v[mid][c1]-v[l1][c1]==w[q])
                                break;
                            else if(v[mid][c1]-v[l1][c1]>w[q])
                                dr = mid-1;
                            else
                                st = mid+1;
                        }
                        if(st<=dr&&m1[v[n][c1]-v[mid][c1]])
                        {
                            m1[v[mid][c1]-v[l1][c1]]--;
                            m1[v[n][c1]-v[mid][c1]]--;
                            l2=mid;
                            for(int q=1; q<=9; q++)
                            {
                                if(m1[w[q]])
                                {
                                    st=c1+1; dr=n;
                                    while(st<=dr)
                                    {
                                        mid = (st+dr)/2;
                                        if(v[l1][mid]-v[l1][c1]==w[q])
                                            break;
                                        else if(v[l1][mid]-v[l1][c1]>w[q])
                                            dr = mid-1;
                                        else
                                            st = mid+1;
                                    }
                                    if(st<=dr&&m1[v[l1][n]-v[l1][c2]])
                                    {
                                        c2=mid;
                                        m1[v[l1][mid]-v[l1][c1]]--;
                                        m1[v[l1][n]-v[l1][c2]]--;
                                        bool ok=1;
                                        if(m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]])
                                            m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]]--;
                                        else
                                            ok=0;
                                        if(m1[v[l2][n]-v[l2][c2]-v[l1][n]+v[l1][c2]])
                                            m1[v[l2][c2]-v[l1][c2]-v[l2][c1]+v[l1][c1]]--;
                                        else
                                            ok=0;
                                        if(m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]])
                                            m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]]--;
                                        else
                                            ok=0;
                                        if(m1[v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]])
                                            m1[v[n][n]-v[n][c2]-v[l2][n]+v[l2][c2]]--;
                                        else
                                            ok=0;
                                        if(ok==1)
                                        {
                                            fout << l1 << " " << l2 << " " << c1 << " " << c2;
                                            return 0;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            for(int q=1; q<=9; q++)
            {
                m1[w[q]] = m2[w[q]];
            }
        }
    }
    return 0;
}