aj30

Untitled

Oct 25th, 2019
45
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  5.  
  6. int main(){
  7. fast;
  8.  
  9. ll t,tcno=0;cin>>t;
  10. while(t--){
  11. ll n,m;cin>>n>>m;
  12. ll a[n];
  13. ll b = 0;
  14. for(ll i=0;i<n;++i){
  15. cin>>a[i];
  16. //b = max(b, (ll)log2l(a[i])+1);
  17. for(ll j=50;j>=0;--j){
  18. if(a[i] & (1ll<<j)){
  19. b = max(b, 1+j);
  20. break;
  21. }
  22. }
  23. }
  24.  
  25. ll ans = 0;
  26. for(ll i=b-1;i>=0;--i){
  27. ll tot = 0;
  28. for(ll j=0;j<n;++j){
  29. if(a[j] & (1ll << i)){
  30. ++tot;
  31. }
  32. }
  33. //cout<<"\nres="<<tot<<endl;
  34. if(tot>n/2){
  35. ans += 1ll << i;
  36. }
  37. }
  38. ll r = 0;
  39. for(ll i=0;i<n;++i){
  40. r+= ans ^ a[i];
  41. }
  42. if(r>m){
  43. cout<<"Case #"<<++tcno<<": "<<-1<<endl;
  44. continue;
  45. }
  46. //cout<<"preans"<<ans<<endl;
  47. for(ll i=b-1;i>=0;--i){
  48. if((ans & (1ll << i))==0){
  49. ll res = 0;
  50. ll x = ans + (1ll <<i);
  51. for(ll j=0;j<n;++j){
  52. res += x ^ a[j];
  53. }
  54. if(res<=m){
  55. ans += (1ll << i);
  56. }
  57. }
  58. }
  59. cout<<"Case #"<<++tcno<<": "<<ans<<endl;
  60. }
  61. return 0;
  62. }
RAW Paste Data