Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.
For permutation p=p0,p1,…,pn, Polo has defined its beauty — number .
Expression means applying the operation of bitwise excluding “OR” to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is represented as “^” and in Pascal — as “xor”.
Help him find among all permutations of integers from 0 to n the permutation with the maximum beauty. Input
The single line contains a positive integer n (1≤n≤106). Output
In the first line print integer m the maximum possible beauty. In the second line print any permutation of integers from 0 to n with the beauty equal to m.
If there are several suitable permutations, you are allowed to print any of them. Sample test(s) Input
4
Output
20 0 2 1 4 3
观察可以发现，两个数异或以后，如果二进制每一位都为1，，那么一定最大，所以我们的策略是，枚举每一个的数
/*************************************************************************> File Name: CF-177-E.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月08日 星期三 16时01分33秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;int per[1001000];int main(){int n;while (~scanf(“%d”, &n)){int use1 = 0, use2 = 0;for (int i = 1; i <= n; ++i){use1 ^= i;}LL ans = 0;int m = n;int high = 0;while (high < n){high = 2 * high + 1;}int use;while (high){use = n;while (use > 0 && high – use <= n){ans += high;per[use] = high – use;use2 ^= (high – use);–use;}high >>= 1;n = use;}per[0] = (use2 ^ use1);ans += per[0];printf(“%I64d\n”, ans);printf(“%d”, per[0]);for (int i = 1; i <= m; ++i){printf(” %d”, per[i]);}printf(“\n”);}return 0;}
志在山顶的人，不会贪念山腰的风景。
