Cod sursa(job #1159211)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 29 martie 2014 13:44:46
Problema Zone Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <cstdio>
#include <algorithm>
using namespace std;
long long i, ss, o, n, p, k, ok, u, d, f, c1, l1, c2, l2, j, w[45], v[45], a[520][520], b[520][520];
int main()
{
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    scanf("%lld", &n);
    for(i=1;i<=9;i++)
        scanf("%lld", &w[i]);
    sort(w+1,w+10);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            scanf("%lld", &a[i][j]);
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
        }
    for(i=1;i<=n;i++)
    {
        l1=i;
        for(j=1;j<=9;j++)
        {
            p=1;
            c1=0;
            u=n;
            ss=w[j];
            while(p<=u)
            {
                k=(p+u)/2;
                if(b[l1][k]==ss)
                {
                    c1=k;
                    break;
                }
                else if(b[l1][k]>ss) u=k-1;
                else p=k+1;
            }
            for(o=1;o<=9;o++)
            {
                if(o!=j)
                {
                    l2=0;
                    p=1;
                    u=n;
                    ss=w[o];
                    while(p<=u)
                    {
                        k=(p+u)/2;
                        if(b[k][c1]-b[l1][c1]==ss)
                        {
                            l2=k;
                            break;
                        }
                        else if(b[k][c1]-b[l1][c1]>ss) u=k-1;
                        else p=k+1;
                    }
                    for(f=1;f<=9;f++)
                    {
                        if(f!=o&&f!=j)
                        {
                            p=1;
                            u=n;
                            ss=w[f];
                            while(p<=u)
                            {
                                k=(p+u)/2;
                                if(b[l2][k]-b[l2][c1]-b[l1][k]+b[l1][c1]==ss)
                                {
                                    c2=k;
                                    break;
                                }
                                else if(b[l2][k]-b[l2][c1]-b[l1][k]+b[l1][c1]>ss) u=k-1;
                                else p=k+1;
                            }


                        v[1]=b[l1][c1];
                        v[2]=b[l2][c1]-b[l1][c1];
                        v[3]=b[l2][c2]-b[l2][c1]-b[l1][c2]+b[l1][c1];
                        v[4]=b[l1][c2]-b[l1][c1];
                        v[5]=b[l1][n]-b[l1][c2];
                        v[6]=b[l2][n]-b[l2][c2]-b[l1][n]+b[l1][l2];
                        v[7]=b[n][c1]-b[l2][c1];
                        v[8]=b[n][c2]-b[n][c1]-b[l2][c2]+b[l2][c1];
                        v[9]=b[n][n]-b[n][c2]-b[l2][n]+b[l2][c2];

                        sort(v+1,v+10);

                        ok=1;
                        for(d=1;d<=9;d++)
                            if(v[d]!=w[d])
                            {
                                ok=0;
                                break;
                            }
                        if(ok==1)
                        {
                            printf("%lld %lld %lld %lld", l1, l2, c1, c2);
                            return 0;
                        }}
                    }
                }
            }
        }
    }
    return 0;
}