Polo the Penguin and XOR Operation

CodeForces-288C

Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.

For permutationp?=?p₀,?p₁,?…,?p_n, Polo has defined its beauty — number $Share a picture$ Expression $Share picture$ xand 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?≤?10⁶).

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.

Examples

Input

Output

20 
0 2 1 4 3
Title: Give a n (1 <= n <= 10^6), find the maximum value of (0 ^ p0) + (1 ^ p1) + (2 ^ p2) +…… + (n ^ pn), where p0 ~ pn are 0 ~ The numbers in n, and each number is used only once.

 1 #include< iostream>
 2 #include
 3 #include< cstring>
 4 #include
 5 #include< algorithm>
 6 using namespace  std;  7 const< /span> int maxn=1e6+10;  8 int n,ans [maxn];  9 int main() 10 { 11 span> scanf("%d"< /span>,&n); 12 memset(ans,-1,sizeof(ans)); 13 for(int i=n; i>=0;i--)  14  {15 if< /span>(ans[i]!=-1) 16 continue; 17 int k1=log2(i)+1;//Find the binary digits of each number and add one digit
18 int k2=(1<1;//Find a number with all 1s and the same digits in binary. 19 //For example Say you know the number 111 with three lower digits and all ones in binary 20 //< /span>Then what you are looking for is actually the XOR of two numbers with three digits to 111, and you know one of them21 //For example, 6 binary digits of 110 are asking for 110^who= 111 So whoever is equivalent to 111^110 
22 
23  ans[k2^i]=i; 24 ans[i]=k2 ^i; 25 }  26 long long sum= 0; 27 for( int i=0;i<=n;i++) 28  {29 sum+=(long long )(i^ans[i]); 30 } 31 span> printf("%lld
 ",sum); 32 for(int i=0;i<=n;i++) 33  {34 if(i) 35  {36 printf(" "); 37  } 38 printf(" %d",ans[i]); 39 } 40 printf("
"); < span style="color: #008080">41 }

Input

Output

20
0 2 1 4 3
The meaning of the question: Given a n (1 <= n <= 10^6), find (0 ^ p0) + (1 ^ p1) + (2 ^ p2) +…… + (n ^ pn) The maximum value of p0 ~ pn is a number from 0 to n, and each number is used only once.

 1 #include< iostream>
 2 #include
 3 #include< cstring>
 4 #include
 5 #include< algorithm>
 6 using namespace  std;  7 const< /span> int maxn=1e6+10;  8 int n,ans [maxn];  9 int main() 10 { 11 scanf("%d",&n); 12 memset(ans,-1,sizeof(ans)); 13 for(int i=n;i> =0;i--) 14< /span>  {15 if(ans[i]!=-1) 16 continue; 17 int  k1=log2(i)+1;//Find the binary digits of each number and add one digit
18 int k2=(1<1; //Find a number with all 1s and the same digits in binary. 19 //For example Say you know the number 111 with three lower digits and all ones in binary 20 //< /span>Then what you are looking for is actually the XOR of two numbers with three digits to 111, and you know one of them21 //For example, 6 binary digits of 110 are asking for 110^who= 111 So whoever is equivalent to 111^110 
22 
23  ans[k2^i]=i; 24 ans[i]=k2 ^i; 25 }  26 long long sum= 0; 27 for( int i=0;i<=n;i++) 28  {29 sum+=(long long )(i^ans[i]); 30 } 31 span> printf("%lld
 ",sum); 32 for(int i=0;i<=n;i++) 33  {34 if(i) 35  {36 printf(" "); 37  } 38 printf(" %d",ans[i]); 39 } 40 printf("
"); < span style="color: #008080">41 }

Input

Input

Output

20
0 2 1 4 3
< span style="font-size: 16px">The meaning of the question: Given a n (1 <= n <= 10^6), find (0 ^ p0) + (1 ^ p1) + (2 ^ p2) +... … + The maximum value of (n ^ pn), where p0 ~ pn are numbers from 0 ~ n, and each number is used only once.

 1 #include< iostream>
 2 #include
 3 #include< cstring>
 4 #include
 5 #include< algorithm>
 6 using namespace  std;  7 const< /span> int maxn=1e6+10;  8 int n,ans [maxn];  9 int main() 10 { 11 scanf("%d",&n); 12 memset(ans,-1,sizeof(ans)); 13 for(int i=n;i> =0;i--) 14< /span>  {15 if(ans[i]!=-1) 16 c ontinue; 17 int< /span> k1=log2(i)+1;//Find the binary digits of each number and add one digit
18 int k2=(1<1;< span style="color: #008000">// Find a number with all 1s and the same digits in binary. 19 //For example Say you know the number 111 with three lower digits and all ones in binary 20 //< /span>Then what you are looking for is actually the XOR of two numbers with three digits to 111, and you know one of them21 //For example, 6 binary digits of 110 are asking for 110^who= 111 So whoever is equivalent to 111^110 
22 
23  ans[k2^i]=i; 24 ans[i]=k2 ^i; 25 }  26 long long sum= 0; 27 for( int i=0;i<=n;i++) 28  {29 sum+=(long long )(i^ans[i]); 30 } 31 span> printf("%lld
 ",sum); 32 for(int i=0;i<=n;i++) 33  {34 if(i) 35  {36 printf(" "); 37  } 38 printf(" %d",ans[i]); 39 } 40 printf("
"); < span style="color: #008080">41 }

Output

 1 #include
< span style="color: #008080"> 2 #include
 3 #include
< span style="color: #008080"> 4 #include
 5 #include
< span style="color: #008080"> 6 using namespace std;  7 const int maxn=1e6+10;  8 int n,ans[maxn];  9 int main() 10 { 11 scanf("%d",&n); 12 memset(ans,-1,sizeof(ans)); 13 for(int i=n;i>=0 ;i--) 14  { span>15 if(ans[i]!=-1) 16 continue; < span style="color: #008080">17 int k1=log2(i)+1 ;//Find the binary digits of each number and add one digit 
18 int k2=( 1<1;//Find a number with all 1s and the same digits in the binary system. 19 //For example Say you know the number 111 with three lower digits and all ones in binary 20 //< /span>Then what you are looking for is actually the XOR of two numbers with three digits to 111, and you know one of them21 //For example, 6 binary digits of 110 are asking for 110^who= 111 So whoever is equivalent to 111^110 
22 
23  ans[k2^i]=i; 24 ans[i]=k2 ^i; 25 }  26 long long sum= 0; 27 for( int i=0;i<=n;i++) 28  {29 sum+=(long long )(i^ans[i]); 30 } 31 span> printf("%lld
 ",sum); 32 for(int i=0;i<=n;i++) 33  {34 if(i) 35  {36 printf(" "); 37  } 38 printf(" %d",ans[i]); 39 } 40 printf("
"); < span style="color: #008080">41 }

bit, computing, operation, Penguin, Polo, thinking, XOR

Polo the Penguin and XOR operation

Leave a Comment Cancel reply