Cod sursa(job #2476496)

Utilizator mihaicivMihai Vlad mihaiciv Data 18 octombrie 2019 23:04:02
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.25 kb
#include<iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

ifstream f("zone.in");
ofstream g("zone.out");

long long n, a[600][600], s[600][600];
long long v[11];

void citire() {
    f >> n;

    for (int i = 0; i < 9; ++i) {
        f >> v[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            f >> a[i][j];
            if (i == 0 && j == 0) {
                s[i][j] = a[i][j];
            } else if (i == 0) {
                s[i][j] = s[i][j - 1] + a[i][j];
            } else if (j == 0) {
                s[i][j] = s[i - 1][j] + a[i][j];
            } else {
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
            }
        }
    }
}

void adauga(int index, long long valoare) {
    v[index] = valoare;
}

void sterge(int index) {
    v[index] = -1;
}

int exista(long long valoare) {
    for (int i = 0; i < 9; ++i) {
        if (v[i] == valoare) return i;
    }
    return -1;
}

void afiseaza_array() {
    for (int i = 0; i < 9; ++i) {
        cout << v[i] << " ";
    }
}

void verify(int row1, int row2, int column1, int column2) {
    //cout << row1 + 1 << " " << row2 + 1 << " " << column1 + 1 << " " << column2 + 1 << "\n";
    long long diff1 = s[row1][column2] - s[row1][column1];
    long long diff2 = s[row2][column2] + s[row1][column1] - s[row1][column2] - s[row2][column1];
    long long diff3 = s[n - 1][column2] + s[row2][column1] - s[row2][column2] - s[n - 1][column1];
    long long diff4 = s[row1][n - 1] - s[row1][column2];
    long long diff5 = s[row2][n - 1] + s[row1][column2] - s[row2][column2] - s[row1][n - 1];
    long long diff6 = s[n - 1][n - 1] + s[row2][column2] - s[n - 1][column2] - s[row2][n - 1];

    int index1 = exista(diff1);
    long long val1 = v[index1];
    if (index1 != -1) {
        sterge(index1);
        int index2 = exista(diff2);
        long long val2 = v[index2];
        if (index2 != -1) {
            sterge(index2);
            int index3 = exista(diff3);
            long long val3 = v[index3];
            if (index3 != -1) {
                sterge(index3);
                int index4 = exista(diff4);
                long long val4 = v[index4];
                if (index4 != -1) {
                    sterge(index4);
                    int index5 = exista(diff5);
                    long long val5 = v[index5];
                    if (index5 != -1) {
                        sterge(index5);
                        //afiseaza_array();
                        int index6 = exista(diff6);
                        if (index6 != -1) {
                            g << row1 + 1 << " " << row2 + 1 << " " << column1 + 1 << " " << column2 + 1;
                            exit(EXIT_SUCCESS);
                        }
                        adauga(index5, val5);
                    }
                    adauga(index4, val4);
                }
                adauga(index3, val3);
            }
            adauga(index2, val2);
        }
        adauga(index1, val1);
    }
}


void cautare3(int row1, int row2, int column1) {
    for (int column2 = column1 + 1; column2 < n; ++column2) {
        verify(row1, row2, column1, column2);
    }
}

void cautare2(int row1, int column1) {
    for (int row2 = row1 + 1; row2 < n; ++row2) {
        int index = exista(s[row2][column1] - s[row1][column1]);
        long long valoare = v[index];
        if (index != -1) {
            sterge(index);
            int index2 = exista(s[n - 1][column1] - s[row2][column1]);
            long long valoare2 = v[index2];
            if (index2 != -1) {
                sterge(index2);
                cautare3(row1, row2, column1);
                adauga(index2, valoare2);
            }
            adauga(index, valoare);
        }
    }
}

int main() {

    citire();

    for (int row1 = 0; row1 < n; ++row1) {
        for (int column1 = 0; column1 < n; ++column1) {
            int index = exista(s[row1][column1]);
            long long valoare = v[index];
            if (index != -1) {
                sterge(index);
                cautare2(row1, column1);
                adauga(index, valoare);
            }
        }
    }

    return 0;
}