Vadim loves filling square tables with integers. But today he came up with a way to do it for fun! Let’s take, for example, a table of size , with rows numbered from top to bottom and columns numbered from left to right. We place in the top left cell, in the bottom right, in the bottom left, and in the top right. That’s all he needs for fun!
Fortunately for Vadim, he has a table of size . He plans to fill it with integers from to in ascending order. To fill such a large table, Vadim will divide it into equal square tables, filling the top left one first, then the bottom right one, followed by the bottom left one, and finally the top right one. Each smaller table will be divided into even smaller ones as he fills them until he reaches tables of size , which he will fill in the order described above.
Now Vadim is eager to start filling the table, but he has questions of two types:
what number will be in the cell at the -th row and -th column;
in which cell coordinates will the number be located.
Help answer Vadim’s questions.
思路
递归，不断缩小边界
AC代码
点击查看代码
```cpp
#define _USE_MATH_DEFINES // To use the definition of cmath
#include
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template
struct custom_hash_base {
size_t operator()(const T& x) const {
static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
return _Hash_bytes(&x, sizeof(x), seed);
}
};
static const auto _ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("../in.txt", "r", stdin);
#endif
return nullptr;
}();
int n, q;
ll d, x, y;
int mpx[5] = {0, 1, 2, 2, 1};
int mpy[5] = {0, 1, 2, 1, 2};
int blocks[2][2] = {
{1, 4},
{3, 2}
};
void find_num(const ll m, ll i = 1, ll j = 1LL << n, const ll mi = 1LL, const ll mx = 1LL << (n << 1)) {
if (mi == mx) {
x = i;
y = j;
return;
}
const ll del = (mx - mi + 1) / 4;
const ll pos = m % del;
const ll block = m / del + (pos != 0);
const ll del2 = sqrt(del);
i += mpx[block] == 2 ? del2 : 0;
j -= mpy[block] == 1 ? del2 : 0;
find_num(pos, i, j, mi + (block - 1) * del, mx - (4 - block) * del);
}
ll get_num(ll i, ll j, const ll mi = 1LL, const ll mx = 1LL << (n << 1)) {
if (mi == mx)
return mi;
const ll del = (mx - mi + 1) / 4;
const ll del2 = sqrt(del);
const ll block = blocks[i > del2][j > del2];
i = i > del2 ? i - del2 : i;
j = j > del2 ? j - del2 : j;
return get_num(i, j, mi + (block - 1) * del, mx - (4 - block) * del);
}
inline void solve() {
// 1 4 13 16
// 3 2 15 14
// 9 12 5 8
// 11 10 7 6
cin >> n >> q;
string spt;
while (q--) {
cin >> spt;
if (spt[0] == '-') {
// q1
cin >> x >> y;
cout << get_num(x, y) << '\n';
} else {
// q2
cin >> d;
find_num(d);
cout << x << ' ' << y << '\n';
}
}
}
int main() {
int T;
for (cin >> T; T > 0; --T) {
solve();
}
return 0;
}
```
