Pagini recente » Cod sursa (job #3359421) | Cod sursa (job #3359431) | Cod sursa (job #3359264) | Cod sursa (job #3359257) | Cod sursa (job #3359427)
#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;
}