Cod sursa(job #1782269)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 17 octombrie 2016 21:45:51
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxN = 550;

int n;
int m;
int p;
int lg[kMaxN];
int c[kMaxN][kMaxN];

void divideConquer(const int fi_x, const int fi_y, const int se_x, const int se_y) {
    if (fi_x <= se_x && fi_y <= se_y) {
        p++;
        int side = 1 << lg[min(se_x - fi_x + 1, se_y - fi_y + 1)];
        for (int i = 0; i < side; i++) {
            for (int j = 0; j < side; j++) {
                c[fi_x + i][fi_y + j] = p;
            }
        }
        divideConquer(fi_x + side, fi_y, se_x, se_y);
        divideConquer(fi_x, fi_y + side, fi_x + side - 1, se_y);
    }
}

int main() {
    freopen("piese.in", "r", stdin);
    freopen("piese.out", "w", stdout);

    for (int i = 2; i < kMaxN; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    
    scanf("%d %d", &n, &m);
    divideConquer(1, 1, n, m);
    printf("%d\n", p);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%d ", c[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}