Cod sursa(job #2482259)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 27 octombrie 2019 22:57:17
Problema Zone Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define N 520
int sel[9],a[N][N],i,j,n,p,l1,l2,c1,c2,x,y;
long long l[N],c[N],zona[9],s[N][N];
vector<long long>v;
vector<int>update;
int pozitie (long long X){
    for (int it = 0; it < 9; ++it)
        if (!sel[it] && zona[it] == X)
        return it;
    return 10;
}
long long val (int i, int j){
    if (i < 0 || j < 0)
        return 0;
    return s[i][j];
}
long long S (int i,int j,int I,int J){
    return s[I][J] - val (i - 1,J) - val (I, j - 1) + val (i - 1, j - 1);
}
bool valid (int l1,int c1,int l2,int c2){
    v.push_back(S(0,c1 + 1,l1,c2));
    v.push_back(S(0,c2 + 1,l1,n - 1));
    v.push_back(S(l1 + 1,c1 + 1,l2,c2));
    v.push_back(S(l1 + 1,c2 + 1,l2,n - 1));
    v.push_back(S(l2 + 1,c1 + 1,n - 1,c2));
    v.push_back(S(l2 + 1,c2 + 1,n - 1,n - 1));
    int pos,it;
    for (it = 0; it < 6; ++it){
        pos = pozitie(v[it]);
        if (pos > 9){
            v.clear();
            for (it = 0; it < 9; ++it)
                if (sel[it] > 1)
                sel[it] = 0;
            return 0;
        }
        else{
            sel[pos] = 2;
        }
    }
    return 1;
}
int main()
{
    ifstream fin ("zone.in");
    ofstream fout ("zone.out");
    fin >> n;
    for (i = 0; i < 9; ++i)
        fin >> zona[i];
    for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j){
        fin >> a[i][j];
        l[i] += a[i][j];
        c[j] += a[i][j];
        if (i > 0 && j > 0)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        else{
            if (i + j < 1)
                s[i][j] = a[i][j];
            if (i > 0)
                s[i][j] = a[i][j] + s[i - 1][j];
            if (j > 0)
                s[i][j] = a[i][j] + s[i][j - 1];
        }
    }
    for (l1 = 0; l1 < n; ++l1)
    for (c1 = 0; c1 < n; ++c1){
        p = pozitie (s[l1][c1]);
        if (p < 9){
            sel[p] = 1;
            for (l2 = l1 + 1; l2 < n; ++l2){
                x = pozitie(S(l1 + 1,0,l2,c1));
                if (x < 9){
                    sel[x] = 1;
                    y = pozitie(S(l2 + 1,0,n - 1,c1));
                    if (y < 9){
                        sel[y] = 1;
                        for (c2 = c1 + 1; c2 < n; ++c2)
                        if (valid (l1,c1,l2,c2)){
                            fout << l1 + 1 << " " << l2 + 1 << " " << c1 + 1 << " " << c2 + 1;
                            return 0;
                        }
                        sel[y] = 0;
                    }
                    sel[x] = 0;
                }
            }
            sel[p] = 0;
        }
    }
    return 0;
}