Cod sursa(job #1466708)

Utilizator akaprosAna Kapros akapros Data 29 iulie 2015 23:06:09
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 514
#define S 9
using namespace std;
int n, i, j, m;
long long a[Nmax][Nmax], s[Nmax][Nmax];
int l1, l2, c1, c2;
long long x[S + 2], y[S + 2], z[S + 2];
void read()
{
    freopen("zone.in", "r", stdin);
    freopen("zone.out", "w", stdout);
    scanf("%d", &n);
    m = n;
    for (i = 1; i <= S; ++ i)
        scanf("%lld", &x[i]);
    sort(x + 1, x + S + 1);
    for (i = 1; i <= S; ++ i)
        z[i] = x[i];
    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= n; ++ j)
            scanf("%lld", &a[i][j]),
                 s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
int ok(long long x[], long long y[])
{
    int i;
    for (i = 1; i < S; ++ i)
        if (x[i] != y[i])
           return 0;
    return 1;
}
int bs(int l1, int c1, int j)
{
    int i = 1, p = 1 << 8;
    while (p)
    {
        if (i + p <= m && s[l1][i + p] - s[l1][c1] <= x[j])
            i += p;
        p /= 2;
    }
    if (s[l1][i] - s[l1][c1] != x[j])
        return 0;
    return i;
}
int BS(int l1, int c1, int j)
{
    int i = 1 + l1, p = 1 << 8;
    while (p)
    {
        if (i + p <= m && s[i + p][c1] - s[l1][c1] <= x[j])
            i += p;
        p /= 2;
    }
    if (s[i][c1] - s[l1][c1] != x[j])
        return 0;
    return i;
}
void solve()
{
    int j, l, k;
    for (l1 = 1; l1 < n - 1; ++ l1)
    {
        for (j = 1; j <= S; ++ j)
        {
            swap(x[j], x[1]);
            c1 = bs(l1, 0, 1);
            if (!c1)
            {
                swap(x[j], x[1]);
                continue;
            }
            for (k = 2; k <= S; ++ k)
            {
                swap(x[k], x[2]);
                l2 = BS(l1, c1, 2);
                if (!l2)
                {
                    swap(x[k], x[2]);
                    continue;
                }
                for (l = 3; l <= S; ++ l)
                {
                    c2 = bs(l1, c1, l);
                    if (!c2)
                        continue;
                    y[1] = s[l1][c1];
                    y[2] = s[l1][c2] - s[l1][c1];
                    y[3] = s[l1][m] - s[l1][c2];
                    y[4] = s[l2][c1] - s[l1][c1];
                    y[5] = s[l2][c2] - s[l1][c2] - s[l2][c1] + s[l1][c1];
                    y[6] = s[l2][m] - s[l1][m] - s[l2][c2] + s[l1][c2];
                    y[7] = s[n][c1] - s[l2][c1];
                    y[8] = s[n][c2] - s[l2][c2] - s[n][c1] + s[l2][c1];
                    y[9] = s[n][m] - s[l2][m] - s[n][c2] + s[l2][c2];
                    sort(y + 1, y + S + 1);
                    if (ok(z, y))
                    {
                        printf("%d %d %d %d", l1, l2, c1, c2);
                        exit(0);
                    }
                }
                swap(x[k], x[2]);
            }
            swap(x[j], x[1]);
        }
    }
}
int main()
{
    read();
    solve();
    return 0;
}