Cod sursa(job #2480335)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 25 octombrie 2019 12:54:03
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.06 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>
#define nmax 520
using namespace std;



class instream {
public:
    instream() {}
    instream(const char *file_name) {
        input_file=fopen(file_name,"r");
        cursor=0;
        fread(buffer,SIZE,1,input_file);
    }
    template <class T>
    inline instream &operator >>(T &n) {
        while((buffer[cursor]<'0'||buffer[cursor]>'9')&&buffer[cursor]!='-') {
            advance();
        }
        int semn=1;
        if (buffer[cursor]=='-')
            semn=-1,advance();
        n=0;
        while('0'<=buffer[cursor]&&buffer[cursor]<='9') {
            n=n*10+buffer[cursor]-'0';
            advance();
        }
        n*=semn;
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE=1<<16;
    int cursor;
    char buffer[SIZE];
    inline void advance() {
        ++ cursor;
        if(cursor==SIZE) {
            cursor=0;
            fread(buffer,SIZE,1,input_file);
        }
    }
};
instream f("zone.in");
ofstream g("zone.out");
vector <int> l_var, c_var;

long long a[10], b[10], c[10];
int v[nmax][nmax], l1s = nmax, l2s, c1s, c2s, n;
long long s[nmax][nmax];


int findin(long long k, int a1, int a2, long long p[])
{
    for (int i = a1; i <= a2; i++)
        if (p[i] == k)
            return true;
    return false;
}
bool ok(int l1, int c1, int l2, int c2)
{
    int i;
    c[1] = s[l1][c1];
    c[2] = s[l1][c2] - c[1];
    c[3] = s[l1][n] - c[1] - c[2];

    c[4] = s[l2][c1] - c[1];
    c[5] = s[l2][c2] - c[1] - c[2] - c[4];
    c[6] = s[l2][n] - c[1] - c[2] - c[3] - c[4] - c[5];

    c[7] = s[n][c1] - c[1] - c[4];
    c[8] = s[n][c2] - c[1] - c[2] - c[4] - c[5] - c[7];
    c[9] = s[n][n] - c[1] - c[2] - c[3] - c[4] - c[5] - c[6] - c[7] - c[8];

    /*
    cout << l1 << ' ' <<  l2  << ' ' << c1 << ' ' << c2 << '\n';
    if (l1 == 1 && c1 == 2) {
        for (i = 1; i <= 9; i++)
            cout << c[i] << ' ';
        cout << '\n';
    }*/

    sort (c + 1 , c + 10);

    for (i = 1; i <= 9; i++)
        if (a[i] != c[i])
            return false;
    return true;
}
void verif_permutation(long long p[])
{
    int l1 = 1, c1 = 1, l2 , c2;
    while (c1 + 2 < n && s[1][c1 + 1] <= p[1])
        c1 ++;
    for (; l1 + 2 < n;) {
        c_var.clear();
        l_var.clear();

        if (s[l1][c1] == p[1]) {
            for (c2 = c1 + 1; c2 < n; c2 ++)
                if (findin(s[l1][c2] - s[l1][c1], 2, 9, p))
                    c_var.push_back(c2);

            for (l2 = l1 + 1; l2 < n; l2 ++)
                if (findin(s[l2][c1] - s[l1][c1], 2, 9, p))
                    l_var.push_back(l2);
        }

        for (int i = 0; i < c_var.size(); i++)
            for (int j  = 0; j < l_var.size(); j++) {
                c2 = c_var[i];
                l2 = l_var[j];
                if (ok(l1, c1, l2, c2)) {
                    if (l1 < l1s || (l1 == l1s && l2 < l2s) || (l1 == l1s && l2 == l2s && c1 + c2 < c1s + c2s)) {
                        l1s = l1;
                        l2s = l2;
                        c1s = c1;
                        c2s = c2;
                    }
                }

            }
        l1 ++;
        while (c1 > 1 && s[l1][c1] > p[1])
            c1--;
    }

}
int main()
{
    int i, j;
    f >> n;
    for (i = 1; i <= 9; i++)
        f >> a[i];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            f >> v[i][j];

    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + 1LL * v[i][j];
    /*
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++)
            cout << s[i][j] << ' ';
        cout << '\n';
    }*/

    for (i = 1; i <= 9; i++)
        b[i] = a[i];

    sort(a + 1, a + 10);

    for (i = 1; i <= 9; i++) {
        swap(b[1], b[i]);
        verif_permutation(b);
        swap(b[i], b[1]);
    }

    g << l1s << ' ' << l2s << ' ' << c1s << ' ' << c2s << '\n';


    return 0;
}