Cod sursa(job #2071980)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 21 noiembrie 2017 11:14:22
Problema Zone Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <algorithm>

FILE *fin = fopen("zone.in", "r"), *fout = fopen("zone.out", "w");

#define BUF_SIZE 1 << 17

int pos = BUF_SIZE;
char buf[BUF_SIZE];

inline char nextch() {
    if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
    return buf[pos++];
}

inline int read() {
    char ch;
    while (!isdigit(ch = nextch()));
    int x = ch - '0';
    while (isdigit(ch = nextch())) x = 10 * x + ch - '0';
    return x;
}

#define ll long long

#define MAXN 512
#define LOGN 8

int n;
bool viz[9], e[9];
ll s[MAXN + 1][MAXN + 1], v[9];

inline bool cauta(ll x) {
    int p = 0;
    while (p < 9 && (e[p] || v[p] != x))
        p++;
    if (p < 9) e[p] = 1;
    return p < 9;
}

inline int cautaL(int l1, int c1, int c2, ll x) {
    int rez = l1 + 1;
    x -= s[l1][c1] - s[l1][c2];
    for (int pas = 1 << LOGN; pas; pas >>= 1)
        if (rez + pas <= n && s[rez + pas][c2] - s[rez + pas][c1] <= x)
            rez += pas;
    return rez;
}

inline int cautaC(int l1, int c1, int l2, ll x) {
    int rez = c1 + 1;
    x -= s[l1][c1] - s[l2][c1];
    for (int pas = 1 << LOGN; pas; pas >>= 1)
        if (rez + pas <= n && s[l2][rez + pas] - s[l1][rez + pas] <= x)
            rez += pas;
    return rez;
}

inline void check4(int l1, int c1, int l2, int c2) {
    for (int i = 0; i < 9; i++)
        e[i] = viz[i];
    bool ok = cauta(s[l1][n] - s[l1][c2]);
    if (ok) {
        ok = cauta(s[n][c1] - s[l2][c1]);
        if (ok) {
            ok = cauta(s[l2][c2] - s[l1][c2] - s[l2][c1] + s[l1][c1]);
            if (ok) {
                ok = cauta(s[n][c2] - s[n][c1] - s[l2][c2] + s[l2][c1]);
                if (ok) {
                    ok = cauta(s[l2][n] - s[l2][c2] - s[l1][n] + s[l1][c2]);
                    if (ok) {
                        ok = cauta(s[n][n] - s[l2][n] - s[n][c2] + s[l2][c2]);
                        if (ok) {
                            fprintf(fout, "%d %d %d %d\n", l1, l2, c1, c2);
                            exit(0);
                        }
                    }
                }
            }
        }
    }
}

inline void check3(int l1, int c1, int l2) {
    for (int i = 0; i < 9; i++) if (viz[i] == 0) {
        int c2 = cautaC(0, c1, l1, v[i]);
        if (s[l1][c2] - s[l1][c1] == v[i]) {
            viz[i] = 1;
            check4(l1, c1, l2, c2);
            viz[i] = 0;
        }
    }
}

inline void check2(int l1, int c1) {
    for (int i = 0; i < 9; i++) if (viz[i] == 0) {
        int l2 = cautaL(l1, 0, c1, v[i]);
        if (s[l2][c1] - s[l1][c1] == v[i]) {
            viz[i] = 1;
            check3(l1, c1, l2);
            viz[i] = 0;
        }
    }
}

inline void check1(int l1) {
    for (int i = 0; i < 9; i++) {
        int c1 = cautaC(0, 0, l1, v[i]);
        if (s[l1][c1] == v[i]) {
            viz[i] = 1;
            check2(l1, c1);
            viz[i] = 0;
        }
    }
}

int main() {
    fscanf(fin, "%d", &n);
    for (int i = 0; i < 9; i++)
        fscanf(fin, "%lld", &v[i]);
    std::sort(v, v + 9);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            s[i][j] = read() + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    for (int l1 = 1; l1 < n; l1++)
        check1(l1);
    return 1;
}