众所周知，\(n\) 位 \(2\) 进制数 \(\overline{a_{n-1}a_{n-2}\cdots a_0}_{(2)}=\sum_{i=0}^{n-1}a_i\times2^i(0\le a_i<2)\)。
那么类似的，可以定义 \(n\) 位 \(-2\) 进制数为 \(\overline{a_{n-1}a_{n-2}\cdots a_0}_{(-2)}=\sum_{i=0}^{n-1}a_i\times(-2)^i(0\le a_i<2)\)。
可以证明对于任意的一个整数，它的 \(-2\) 进制表示唯一，现在给出一个整数 \(n\)，求其 \(-2\) 进制表示（\(-10^9\le n\le10^9\)）。
你说的对，但是这种有加有减的让我很不舒服，我也不喜欢用脑子想简便方法因为不会，所以想到了一种比较长，但是显然而且不用思考的方法。
我们从 \(-2\) 进制数的定义出发，我们发现一个数的 \(-2\) 进制表示出的数值其实是把这个数的偶数位拎出来，所表示的二进制数的十进制数值，减去把这个数的奇数位拎出来，所表示的二进制数的十进制数值（下标从 \(0\) 开始）。
栗：\(-9\) 的 \(-2\) 进制是 \(1011_{(-2)}\)，把偶数位拎出来，是 \(0001_{(2)}\)，也就是 \(1_{(10)}\)，把奇数位拎出来，是 \(1010_{(2)}\)，也就是 \(10_{(10)}\)，然后用 \(1\) 减去 \(10\)，就是 \(-9\)。
这给我们一个启发，或许我们可以通过数位的奇偶分开讨论来凑这个数字？在这之前我们首先要设定一个合适的阈值，使其不会爆也可以涵盖我们值域内的所有数字。此处我选择的数是 \(33\) 位的 \(-2\) 进制数。
不难发现一个 \(33\) 位的 \(-2\) 进制数的值域是 \([-2863311530,1431655766]\)，正好包含了题目中 \(n\) 的取值范围，同时也是最小的，复杂度一会分析。
下面介绍做法。
既然是偶数位所表示的减去奇数位所表示的，那么我们不难想到取暴力枚举所有奇数位是 \(0\)（也就是偶数位可以为 \(1\)）的数和所有偶数位是 \(0\) 的数，可以存入两个 set 中（至于为什么想到 set，我也不知道）。
不难看出这样的复杂度上界应该大概是 \(2\times2^{16}=2^{17}\)。
现在我们需要的就是从这两个集合中选数，来凑出 \(n\)，我们以 \(n>0\) 时为例，这时我们要求偶数位所表示的减去奇数位表示的（就是这个 \(n\)）是一个正值，那么我们首先利用 upper_bound 查找出第一个 set（这个存的是偶数位可以不为 \(0\) 的全体数）中最前的数值大于 \(n\) 的位置 \(loc\)，那么只有这个 set 中 \(loc\) 以及往后的值才有可能配出 \(n\)。
那么接下来我们遍历 \(loc\) 以及之后的数值 \(m\)，那么我们在第二个 set 中查找是否存在 \(m-n\) 这个数值即可。
\(n<0\) 时同理，只是第一个和第二个反过来了。
遍历的总复杂度不会超过 s1.size () 和 s2.size () 的较大者，复杂度上界是 \(2^{16}\)，加上预处理的复杂度仍然绰绰有余。
最后假设第一个中找到的数是 \(x_1\)，第二个中找到的是 \(x_2\)，那么我们这个数的 \(-2\) 进制表示就是 \(x_1\) 和 \(x_2\) 的二进制表示中所有为 \(1\) 的位的或。
代码：
inline void pre(int loc, int num, bool flag) {
if (loc > 32)
return (void)(flag ? s2.insert(num) : s1.insert(num));
pre(loc + 2, num, flag);
pre(loc + 2, num + (1ll << loc), flag);
} // 搜索奇、偶位，每次加 2 可以大大降低复杂度
inline void out1(int x) {
while (x) {
stk[++stop] = (x & 1);
x >>= 1;
}
while (stop) {
cout << stk[stop--];
}
cout << '\n';
exit(0);
}
inline void out2(int a, int b) {
while (a || b) {
stk[++stop] = (a & 1 | b & 1);
a >>= 1;
b >>= 1;
}
while (stop) {
cout << stk[stop--];
}
cout << '\n';
exit(0);
}
read(n);
if (n == 0)
return puts("0"), 0;
// m = ceil ((double) __lg (abs (n))) ;
// if (1ll << m != abs (n)) m ++ ;
pre(0, 0, 0), pre(1, 0, 1);
if (n > 0 && s1.count(n))
out1(n);
else if (n < 0 && s2.count(abs(n)))
out1(abs(n));
// 可以直接输出
if (n > 0) {
auto it1 = s1.upper_bound(n); // 迭代器遍历
for (; it1 != s1.end(); it1++) {
if (s2.count(*it1 - n)) {
// auto it2 = s2.lower_bound (*it1 - n) ;
out2(*it1, *it1 - n);
}
}
} else {
n = abs(n); // 别忘了加绝对值
// cout << n << '\n' ;
auto it2 = s2.upper_bound(n);
for (; it2 != s2.end(); it2++) {
if (s1.count(*it2 - n)) {
// cout << *it2 - n << '\n' ;
// auto it1 = s2.lower_bound (*it2 - n) ;
// cout << *it1 << ' ' << *it2 << '\n' ;
out2(*it2 - n, *it2);
}
}
}