Cod sursa(job #3254816)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 8 noiembrie 2024 21:22:57
Problema Zone Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.72 kb
#include <fstream>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin("zone.in");
ofstream fout("zone.out");
unordered_map <int, int> m1, m2;
int v[1000][1000], w[100];
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]);
        }
    }
    sort(w+1, w+10);
    for(int i=1; i<=n-2; i++)
    {
        for(int q=1; q<=9; q++)
        {
            st=0, dr=n+1, mid;
            while(st<dr-1)
            {
                mid=(st+dr)/2;
                if(v[i][mid]<w[q])
                    st = mid;
                else
                    dr = mid;
            }
            if(v[i][dr]==w[q])
            {
                l1=i;
                c1=dr;
                m1[v[l1][c1]]--;
                for(int q=1; q<=9; q++)
                {
                    if(m1[w[q]])
                    {
                        st=l1; dr=n+1;
                        while(st<dr-1)
                        {
                            mid = (st+dr)/2;
                            if(v[mid][c1]-v[l1][c1]<w[q])
                                st = mid;
                            else
                                dr = mid;
                        }
                        if(v[dr][c1]-v[l1][c1]==w[q]&&m1[v[n][c1]-v[dr][c1]])
                        {
                            m1[v[dr][c1]-v[l1][c1]]--;
                            m1[v[n][c1]-v[dr][c1]]--;
                            l2=dr;
                            for(int q=1; q<=9; q++)
                            {
                                if(m1[w[q]])
                                {
                                    st=c1; dr=n+1;
                                    while(st<dr-1)
                                    {
                                        mid = (st+dr)/2;
                                        if(v[l1][mid]-v[l1][c1]<w[q])
                                            st = mid;
                                        else
                                            dr = mid;
                                    }
                                    if(v[l1][dr]-v[l1][c1]==w[q]&&m1[v[l1][n]-v[l1][c2]])
                                    {
                                        c2=dr;
                                        m1[v[l1][dr]-v[l1][c1]]--;
                                        m1[v[l1][n]-v[l1][c2]]--;
                                        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]]--;
                                            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]]--;
                                                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]]--;
                                                    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]]--;
                                                        fout << l1 << " " << l2 << " " << c1 << " " << c2;
                                                        return 0;
                                                    }
                                                    m1[v[n][c2]-v[n][c1]-v[l2][c2]+v[l2][c1]]++;
                                                }
                                                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]]++;
                                        }
                                        m1[v[l1][dr]-v[l1][c1]]++;
                                        m1[v[l1][n]-v[l1][c2]]++;
                                    }
                                }
                            }
                            m1[v[dr][c1]-v[l1][c1]]++;
                            m1[v[n][c1]-v[dr][c1]]++;
                        }
                    }
                }
                m1[v[l1][c1]]++;
            }
        }
    }
    return 0;
}