比赛 NOIP模拟赛1 评测结果 AAAWWWWWWW
题目名称 异或 最终得分 30
用户昵称 Kyru Yann 运行时间 0.323 s
代码语言 C++ 内存使用 0.56 MiB
提交时间 2018-02-08 21:19:01
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <stack>
  11. #include <vector>
  12. #include <cctype>
  13. #include <iomanip>
  14. #define inf 0x7f7f7f7f
  15. using namespace std;
  16. int n,k,a[100005],nums=0,ret,blk,block_upper[50]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432};
  17. struct data
  18. {
  19. int val;
  20. friend bool operator < (data a,data b)
  21. {
  22. return a.val>b.val;
  23. }
  24. };
  25. priority_queue<data>pq;
  26. int find_block(int x)
  27. {
  28. ret=block_upper[(int)ceil((double)log(x)/log(2))];
  29. if(ret==x) return ret*2;
  30. return ret;
  31. }
  32. int main()
  33. {
  34. freopen("xorxor.in","r+",stdin);
  35. freopen("xorxor.out","w+",stdout);
  36. scanf("%d%d",&n,&k);
  37. for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  38. sort(a+1,a+1+n);
  39. if(n<=500)
  40. {
  41. for(int i=1;i<n;i++)
  42. for(int j=i+1;j<=n;j++) pq.push((data){a[i]^a[j]});
  43. for(int i=1;i<k;i++) pq.pop();
  44. cout<<pq.top().val<<endl;
  45. }
  46. else
  47. {
  48. for(int i=1;i<=n && nums<=500005;i++)
  49. {
  50. int j;
  51. blk=find_block(a[i]);
  52. for(j=i+1;j<=n && a[j]<blk && nums<=500005;j++)
  53. {
  54. pq.push((data){a[i]^a[j]});
  55. nums++;
  56. }
  57. pq.push((data){a[i]^a[j++]});
  58. pq.push((data){a[i]^a[j++]});
  59. pq.push((data){a[i]^a[j++]});
  60. pq.push((data){a[i]^a[j++]});
  61. pq.push((data){a[i]^a[j++]});
  62. nums+=5;
  63. }
  64. for(int i=1;i<k;i++) pq.pop();
  65. cout<<pq.top().val<<endl;
  66. }
  67. return 0;
  68. }
  69.