Description:

You have a complete bipartite graph where each part contains exactly n nodes, numbered from 0 to n - 1 inclusive.

The weight of the edge connecting two vertices with numbers x and y is img (bitwise AND).

Your task is to find a minimum cost perfect matching of the graph, i.e. each vertex on the left side matches with exactly one vertex on the right side and vice versa. The cost of a matching is the sum of cost of the edges in the matching.

img denotes the bitwise AND operator. If you’re not familiar with it, see {https://en.wikipedia.org/wiki/Bitwise_operation#AND}.

Input:

The input contains a single integer n (1 ≤ n ≤ 5 * 1 0 5 10^5 105).

Output:

Output n space-separated integers, where the i-th integer denotes pi (0 ≤ pi ≤ n - 1, the number of the vertex in the right part that is matched with the vertex numbered i in the left part. All pi should be distinct.

Your answer is correct if and only if it is a perfect matching of the graph with minimal cost. If there are multiple solutions, you may output any of them.

Sample Input:

3

Sample Output:

0 2 1

Hint:

For n = 3, p0 = 0, p1 = 2, p2 = 1 works. You can check that the total cost of this matching is 0, which is obviously minimal.

题目链接

dfs暴力搜索易观察得最小值均为0,当 ( x ) = y (\sim x)=y时 (x)=yx\land y$(bitwise AND)取得最小值 0 0 0,所以连接的线可以均为 ( x ) = y (\sim x)=y (x)=y,且若 x x x y y y相连,则 y y y也与 x x x相连,枚举 x x x找相应的 y y y即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout << #x << "=" << x << endl;
#define ArrayDebug(x,i) cout << #x << "[" << i << "]=" << x[i] << endl;
#define print(x) out(x);putchar('\n');
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (read(n)) {
		vector<bool> vis(n, 0);
		vector<int> ans(n, -1);
		for (int i = n - 1; i >= 0; --i) {
			if (vis[i]) {
				continue;
			}
			bitset<20> sys = i;
			int len = log2(i) + 1;
			for (int j = 0; j < len; ++j) {
				sys[j] = sys[j] == 1 ? 0 : 1;
			}
			int temp = int(sys.to_ulong());
			if (temp < n && temp >= 0 && !vis[temp]) {
				ans[i] = temp;
				ans[temp] = i;
				vis[i] = vis[temp] = 1;
			}
		}
		for (int i = 0; i < n; ++i) {
			out(ans[i]);
			if (i != n - 1) {
				putchar(' ');
			}
		}
		putchar('\n');
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}