HDU5014

贪心YY下就可以了。最后肯定是两两配对的。从大到小去找配对的。异或以下就可以了。比如要找x配对的。因为是x最高位以下的0变1,1变0，这个值一定是比x小的。注意最后需要long long.

Number Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 629 Accepted Submission(s): 297 Special Judge

Problem Description

There is a special number sequence which has n+1 integers. For each number in sequence, we have two rules: ● ai ∈ [0,n] ● ai ≠ aj( i ≠ j ) For sequence a and sequence b, the integrating degree t is defined as follows(“⊕” denotes exclusive or):

t = (a0 ⊕ b0) + (a1 ⊕ b1) +···+ (an ⊕ bn)

(sequence B should also satisfy the rules described above) Now give you a number n and the sequence a. You should calculate the maximum integrating degree t and print the sequence b.

Input

There are multiple test cases. Please process till EOF. For each case, the first line contains an integer n(1 ≤ n ≤ 105), The second line contains a0,a1,a2,…,an.

Output

For each case, output two lines.The first line contains the maximum integrating degree t. The second line contains n+1 integers b0,b1,b2,…,bn. There is exactly one space between bi and bi+1(0 ≤ i ≤ n - 1). Don’t ouput any spaces after bn.

Sample Input

4 2 0 1 4 3

Sample Output

20 1 0 2 3 4

Source

2014 ACM/ICPC Asia Regional Xi’an Online

/* ***
Author :kuangbin
Created Time :2014/9/15 22:00:04
File Name :E:\2014ACM\2014网络赛\2014西安\HDU5014.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 100010;
int a[MAXN];
int b[MAXN];
bool vis[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
for(int i = 0;i <= n;i++)scanf(“%d”,&a[i]);
memset(vis,false,sizeof(vis));
for(int i = n;i >= 0;i–)
if(!vis[i]){
vis[i] = true;
if(i == 0){
b[0] = 0;
continue;
}
int x = (1<<20);
while((i&x) == 0)x >>= 1;
//printf(“i %d %d\n”,i,x);
x = 2*x-1;
x = x^i;
//printf(“%d\n”,x);
b[i] = x;
b[x] = i;
vis[x] = true;
}
long long ans = 0;
for(int i = 0;i <= n;i++)ans += (i^b[i]);
printf(“%I64d\n”,ans);
for(int i = 0;i <= n;i++){
printf(“%d”,b[a[i]]);
if(i == n)printf(“\n”);
else printf(“ “);
}
}
return 0;
}