Cod sursa(job #3359427)

Utilizator rares89_Dumitriu Rares rares89_ Data 27 iunie 2026 21:05:10
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xcopy.in");
ofstream fout("xcopy.out");

const int BUFSIZE = 1 << 20;

int n, m;
char buf[BUFSIZE];
int ptr;

void flush() {
    fout.write(buf, ptr);
    ptr = 0;
}

void putch(char c) {
    if(ptr == BUFSIZE) {
        flush();
    }

    buf[ptr++] = c;
}

void writeint(int x) {
    char s[15];
    int l = 0;

    if(x == 0) {
        putch('0');
        return;
    }

    while(x) {
        s[l++] = char('0' + x % 10);
        x /= 10;
    }

    while(l--) {
        putch(s[l]);
    }
}

int bits(int x) {
    int r = 0;

    x--;

    while(x) {
        r++;
        x >>= 1;
    }

    return r;
}

vector<int> path_gray(int n) {
    if(n == 1) {
        return {0};
    }

    int p = 1;

    while((p << 1) <= n) {
        p <<= 1;
    }

    if(p == n) {
        vector<int> v;

        for(int i = 0; i < n; i++) {
            v.push_back(i ^ (i >> 1));
        }

        return v;
    }

    int rest = n - p;
    vector<int> a = path_gray(rest);
    vector<int> ans;

    for(int x : a) {
        ans.push_back(x | p);
    }

    int start = a.back();

    for(int i = 0; i < p; i++) {
        ans.push_back(start ^ (i ^ (i >> 1)));
    }

    return ans;
}

int take(int mask, int cnt) {
    int r = 0;

    while(cnt--) {
        int bit = mask & -mask;
        r |= bit;
        mask ^= bit;
    }

    return r;
}

int bestval(int len, int mask) {
    if(len <= 1) {
        return 0;
    }

    int lg = 31 - __builtin_clz(len);
    int p = 1 << lg;

    if(p == len) {
        return take(mask, lg);
    }

    int low = take(mask, lg);
    int top = take(mask, lg + 1) ^ low;

    return top | bestval(len - p, low);
}

int spread(int x, int mask) {
    int r = 0;

    while(x) {
        int bit = mask & -mask;

        if(x & 1) {
            r |= bit;
        }

        x >>= 1;
        mask ^= bit;
    }

    return r;
}

int main() {
    fin >> n >> m;

    int bn = bits(n);
    int bm = bits(m);
    int d = bn + bm;
    int all = (1 << d) - 1;

    int best = 1000000000;
    int bestn = 0, bestm = 0;

    for(int mask = 0; mask <= all; mask++) {
        if(__builtin_popcount(mask) != bn) {
            continue;
        }

        int other = all ^ mask;
        int val = bestval(n, mask) + bestval(m, other);

        if(val < best) {
            best = val;
            bestn = mask;
            bestm = other;
        }
    }

    vector<int> lin = path_gray(n);
    vector<int> col = path_gray(m);

    for(int i = 0; i < n; i++) {
        lin[i] = spread(lin[i], bestn);
    }

    for(int j = 0; j < m; j++) {
        col[j] = spread(col[j], bestm);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(j) {
                putch(' ');
            }

            writeint(lin[i] | col[j]);
        }

        putch('\n');
    }

    flush();

    return 0;
}