{"id":1443,"date":"2013-04-03T02:01:45","date_gmt":"2013-04-02T18:01:45","guid":{"rendered":"https:\/\/blog.rexdf.org\/?p=1443"},"modified":"2013-04-03T02:01:45","modified_gmt":"2013-04-02T18:01:45","slug":"codeforces-177-e","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/en\/2013\/04\/codeforces-177-e\/","title":{"rendered":"Codeforces 177 E"},"content":{"rendered":"
\n
\u00a0Polo the Penguin and XOR operation<\/div>\n
\n
time limit per test<\/div>\n

2 seconds<\/p><\/div>\n

\n
memory limit per test<\/div>\n

256 megabytes<\/p><\/div>\n

\n
input<\/div>\n

standard input<\/p><\/div>\n

\n
output<\/div>\n

standard output<\/p><\/div>\n<\/div>\n

\n

Little penguin Polo likes permutations. But most of all he likes permutations of integers from\u00a00\u00a0to\u00a0n<\/i>, inclusive.<\/p>\n

For permutation\u00a0p<\/i>\u2009=\u2009p<\/i>0<\/sub>,\u2009p<\/i>1<\/sub>,\u2009…,\u2009p<\/i>n<\/i><\/sub>, Polo has defined its beauty \u2014 number\u00a0\"\"

Expression\u00a0\"\"

Help him find among all permutations of integers from\u00a00\u00a0to\u00a0n<\/i>\u00a0the permutation with the maximum beauty.<\/p>\n<\/div>\n

\n
Input<\/div>\n

The single line contains a positive integer\u00a0n<\/i>\u00a0(1\u2009\u2264\u2009n<\/i>\u2009\u2264\u2009106<\/sup>).<\/p>\n<\/div>\n

\n
Output<\/div>\n

In the first line print integer\u00a0m<\/i>\u00a0the maximum possible beauty. In the second line print any permutation of integers from\u00a00\u00a0to\u00a0n<\/i>\u00a0with the beauty equal to\u00a0m<\/i>.<\/p>\n

If there are several suitable permutations, you are allowed to print any of them.<\/p>\n<\/div>\n

\n
Sample test(s)<\/div>\n
\n
\n
input<\/div>\n
4<\/pre>\n<\/div>\n
\n
output<\/div>\n
20 0 2 1 4 3<\/pre>\n<\/div>\n<\/div>\n<\/div>\n
\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstdlib>\r\n\r\nusing namespace std;\r\n\r\nint a[1000005];\r\nint vis[1000005];\r\n\r\nint main()\r\n{\r\n    int n,mask=0,tmp_p,p=1;\r\n    int tmp;\r\n    long long sum=0;\r\n    cin>>n;\r\n    while(p<=n)\r\n    {\r\n        mask|=p;\r\n        p<<=1;\r\n    }\r\n    \/\/cout<<mask<<endl;\r\n    for(int i=n;i;i--)\r\n      if(0==vis[i])\r\n      {\r\n          tmp=((~i)&mask);\r\n          \/\/cout<<i<<" find "<<tmp<<endl;\r\n          if(tmp<=n)\r\n          {\r\n              vis[i]=1;\r\n              vis[tmp]=1;\r\n              sum+=mask<<1;\r\n              a[i]=tmp;\r\n              a[tmp]=i;\r\n          }\r\n          else\r\n          {\r\n              tmp_p=1;\r\n              \/\/tmp=((~i)&(mask>>1));\r\n              while((1<<tmp_p)<=mask)\r\n              {\r\n                  tmp=((~i)&(mask>>tmp_p));\r\n                  if(0==vis[tmp])break;\r\n                  tmp_p++;\r\n              }\r\n              vis[tmp]=1;\r\n              vis[i]=1;\r\n              sum+=(tmp^i)<<1;\r\n              a[i]=tmp;\r\n              a[tmp]=i;\r\n          }\r\n      }\r\n    cout<<sum<<endl;\r\n    if(vis[0])cout<<a[0];\r\n    else cout<<0;\r\n    for(int i=1;i<=n;i++)\r\n      cout<<" "<<a[i];\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u00a0Polo the Penguin and XOR operation time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Little penguin Polo likes permutations. But most of all he likes permutations of integers from\u00a00\u00a0to\u00a0n, inclusive. … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[125],"class_list":["post-1443","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-codeforces"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts\/1443","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/comments?post=1443"}],"version-history":[{"count":0,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/posts\/1443\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/media?parent=1443"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/categories?post=1443"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rexdf.org\/en\/wp-json\/wp\/v2\/tags?post=1443"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}