Cod sursa(job #849050)

Utilizator vendettaSalajan Razvan vendetta Data 6 ianuarie 2013 00:15:06
Problema Zone Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 513
#define Cifmax (1<<14)
#define ll long long

ll aux[10], s[nmax][nmax];
int n, a[10];
vector<int> lista[10];
char S[Cifmax];
int poz = 0;
void buf(int &nr){
    nr = 0;
    while( (S[poz]<'0' || S[poz]>'9') && S[poz] != '-') {
        ++poz;
        if (poz == Cifmax){
            fread(S, 1, Cifmax, stdin);
            poz = 0;
        }
    }
    int semn = 1;
    if (S[poz] == '-'){
        ++poz; semn = -1;
        if (poz == Cifmax){
            fread(S, 1, Cifmax, stdin);
            poz = 0;
        }
    }

    while( S[poz] >= '0' && S[poz]<='9' ){
        nr = nr * 10 + (S[poz] - '0');
        ++poz; if (poz == Cifmax){
            fread(S, 1, Cifmax, stdin);
            poz = 0;
        }
    }
}

void citeste(){
    buf(n);
    for(int i=1; i<=9; ++i) buf(a[i]);
    sort(a+1, a+10);

    int x; int ord = 0;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            ++ord; buf(x);
            s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + (ll)x;
            for(int k=1; k<=9; ++k){
                if (s[i][j] == a[k]){
                    lista[k].push_back(ord); break;
                }
            }
        }
    }
}

int fax(int x){
    if (x <= n) return 1;
    if (x % n == 0) return x/n;
    return x/n+1;
}
int fay(int y){
    y = y % n;
    if (y == 0) return n;
    return y;
}

inline bool baga_sume(int poz, int x1, int y1, int x4, int y4){
    //poz e luata
    int x2 = x1; int y2 = y4;
    int x3 = x4; int y3 = y1;
    aux[0] = 0;
    aux[1] = s[x1][y1];
    aux[2] = s[x2][y2] - s[x1][y1];
    aux[3] = s[x2][n] - s[x2][y2];
    aux[4] = s[x3][y3] - s[x1][y1];
    aux[5] = s[x4][y4] - s[x2][y2] - s[x3][y3] + s[x1][y1];
    aux[6] = s[x4][n] - s[x2][n] - s[x4][y4] + s[x2][y2];
    aux[7] = s[n][y1] - s[x4][y1];
    aux[8] = s[n][y4] - s[x4][y4] - s[n][y1] + s[x3][y3];
    aux[9] = s[n][n] - s[x4][n] - s[n][y4] + s[x4][y4];
    sort(aux+1, aux+10);
    for(int i=1; i<=9; ++i){
        if (aux[i] != a[i]) return 0;
    }
    return 1;
}

void rezolva(){
    for(int i=2; i<n; ++i){
        for(int j=2; j<n; ++j){// (i,j) e coltul dreapta jos al patratului din centru
            for(int k=1; k<=9; ++k){
                for(int w=0; w<lista[k].size(); ++w){
                    int x = fax(lista[k][w]); int y = fay(lista[k][w]);
                    if (x >= 1 && y >= 1 && x < i && y < j){
                        if (baga_sume(k, x, y, i, j) == 1){
                            g << x << " " << i << " " << y << " "<<j << "\n";
                            return;
                        }
                    }
                }
            }
        }
    }
}

int main(){
    freopen("zone.in", "r", stdin);

    citeste();
    rezolva();

    g.close();

    return 0;
}