Snapper_001

Untitled

Nov 18th, 2024
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.42 KB | None | 0 0
  1. void solve(){
  2. ll n;
  3. cin>>n;
  4. set<ll>A;
  5. for(int i=0;i<n;i++){
  6. ll x;
  7. cin>>x;
  8. A.insert(x);
  9. }
  10. unordered_map<ll,set<ll>>mp;
  11.  
  12. ll till_or = 0;
  13. ll iter = 0;
  14. ll ans = 1;
  15. for(int bit = 30 ; bit>=0;bit--){
  16.  
  17. vector<vector<ll>>nxt(1 , vector<ll>(31));
  18. ll id = 1;
  19. for(auto it : A){
  20. ll node = 0;
  21.  
  22. for(int j = 30 ; j>=0;j--){
  23. ll c = 0;
  24. if(it&(1ll<<j)) c= 1;
  25. if(nxt[node][c] == 0){
  26. nxt.push_back(vector<ll>(31));
  27. nxt[node][c] = id++;
  28. }
  29. node = nxt[node][c];
  30. }
  31. }
  32.  
  33. ll node = 0;
  34. ll max_make = 0;
  35. for(int j = 30 ; j>=0;j--){
  36. if(nxt[node][1] != 0){
  37. node = nxt[node][1];
  38. max_make += (1ll<<j);
  39. }
  40. else{
  41. node = nxt[node][0];
  42. }
  43. }
  44.  
  45. if(max_make == 0){
  46. break;
  47. }
  48.  
  49. iter++;
  50. till_or |= max_make;
  51. ans *= (till_or);
  52.  
  53. set<ll>new_A;
  54. for(auto it : A){
  55. ll new_val = (it - (it&till_or));
  56. new_A.insert(new_val);
  57. }
  58. A.swap(new_A);
  59. }
  60.  
  61. for(int j = iter ; j < n ; j++){
  62. ans *= till_or;
  63. }
  64. cout << ans << endl;
  65.  
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment