Cod sursa(job #1688566)

Utilizator akaprosAna Kapros akapros Data 13 aprilie 2016 16:24:48
Problema Piese Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define maxN 502
using namespace std;
int n, m, k, a[maxN][maxN], ans;
void read()
{
    k = 0;
    freopen("piese.in", "r", stdin);
    scanf("%d %d", &n, &m);
    while ((1 << (k + 1)) <= n && (1 << (k + 1)) <= m)
        ++ k;
}
void det_ans(int k, int x, int y, int z, int t)
{
    int i, j, p, q, l = 1 << k;
    int px = (z - x + 1) / l, py = (t - y + 1) / l;
    if (x == z)
    {
        for (i = y; i <= t; ++ i)
            a[x][i] = ++ ans;
        return ;
    }
    if (y == t)
    {
        for (i = x; i <= z; ++ i)
            a[i][y] = ++ ans;
        return ;
    }

    for (i = x; i + l - 1 <= z; i += l)
        for (j = y; j + l - 1 <= t; j += l)
        {
            ++ ans;
            for (p = 0; p < l; ++ p)
                for (q = 0; q < l; ++ q)
                    a[i + p][j + q] = ans;
        }
    if (px * l + x - 1 < z)
        det_ans(k - 1, px * l + x, y, z, t);
    if (py * l + y - 1 < t)
        det_ans(k - 1, x, py * l + y, px * l + x - 1, t);
}
void solve()
{
    int i, j;
    det_ans(k, 1, 1, n, m);
}
void write()
{
    int i, j;
    freopen("piese.out", "w", stdout);
    printf("%d\n", ans);
    for (i = 1; i <= n; ++ i)
    {
        for (j = 1; j <= m; ++ j)
            printf("%d ", a[i][j]);
        printf("\n");
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}