Feed
2 seconds
256 megabytes
standard input
standard output
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.
The single line contains a positive integer n (1 ≤ n ≤ 106).
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.
4
20 0 2 1 4 3
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[1000005];
int vis[1000005];
int main()
{
int n,mask=0,tmp_p,p=1;
int tmp;
long long sum=0;
cin>>n;
while(p<=n)
{
mask|=p;
p<<=1;
}
//cout<<mask<<endl;
for(int i=n;i;i--)
if(0==vis[i])
{
tmp=((~i)&mask);
//cout<<i<<" find "<<tmp<<endl;
if(tmp<=n)
{
vis[i]=1;
vis[tmp]=1;
sum+=mask<<1;
a[i]=tmp;
a[tmp]=i;
}
else
{
tmp_p=1;
//tmp=((~i)&(mask>>1));
while((1<<tmp_p)<=mask)
{
tmp=((~i)&(mask>>tmp_p));
if(0==vis[tmp])break;
tmp_p++;
}
vis[tmp]=1;
vis[i]=1;
sum+=(tmp^i)<<1;
a[i]=tmp;
a[tmp]=i;
}
}
cout<<sum<<endl;
if(vis[0])cout<<a[0];
else cout<<0;
for(int i=1;i<=n;i++)
cout<<" "<<a[i];
return 0;
}