Advertisement
pratiyush7

Untitled

Oct 6th, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ull unsigned long long int
  3. #define ll long long int
  4. #define LL_MAX 9223372036854775807
  5. #define pb push_back
  6. #define pf push_front
  7. #define mp make_pair
  8. #define popb pop_back
  9. #define vl vector<ll>
  10. #define bs(v, x) binary_search(v.begin(), v.end(), x)
  11. #define popf pop_front
  12. #define p() cout << '\n'
  13. #define p0(x) cout << x << " "
  14. #define p1(x) cout << x << '\n'
  15. #define p2(x, y) cout << x << " " << y << '\n'
  16. #define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
  17. #define printv(v) \
  18. for (ll i = 0; i < v.size(); ++i) \
  19. cout << v[i] << " "; \
  20. cout << '\n'
  21. #define pr1(x) cout << fixed << setprecision(15) << x << '\n'
  22. #define mod 1000000007
  23. #define mod1 998244353
  24. #define fio \
  25. ios_base::sync_with_stdio(false); \
  26. cin.tie(NULL)
  27. #define get(n) \
  28. ll n; \
  29. cin >> n
  30. #define getvec(v, n) \
  31. vector<ll> v(n); \
  32. for (ll i = 0; i < n; i++) \
  33. cin >> v[i];
  34. #define getstr(s) \
  35. string s; \
  36. cin >> s
  37. #define all(x) x.begin(), x.end()
  38. #define countBits(x) __builtin_popcount(x)
  39. using namespace std;
  40.  
  41. class Node
  42. {
  43. public:
  44. Node *left;
  45. Node *right;
  46. int val{0};
  47. };
  48.  
  49. void add(ll x, Node *head)
  50. {
  51. head->val = head->val + 1;
  52. for (ll i = 30; i >= 0; i--)
  53. {
  54. ll curr = (1 << i) & x;
  55. if (curr == 0)
  56. {
  57. if (!head->left)
  58. {
  59. Node *node = new Node();
  60. head->left = node;
  61. }
  62. head = head->left;
  63. head->val = head->val + 1;
  64. }
  65. else
  66. {
  67. if (!head->right)
  68. {
  69. Node *node = new Node();
  70. head->right = node;
  71. }
  72. head = head->right;
  73. head->val = head->val + 1;
  74. }
  75. }
  76. }
  77.  
  78. ll query(ll x, Node *head)
  79. {
  80. head->val = head->val - 1;
  81. ll ans = 0;
  82. for (ll i = 30; i >= 0; i--)
  83. {
  84. ll curr = (1ll << i) & x;
  85. //p2(ans, curr);
  86. if (curr == 0)
  87. {
  88. if (!head->left || (head->left && head->left->val <= 0))
  89. {
  90. head = head->right;
  91. head->val = head->val - 1;
  92. ans = (ans + (1ll << i));
  93. }
  94. else
  95. {
  96. head = head->left;
  97. head->val = head->val - 1;
  98. }
  99. }
  100. else
  101. {
  102. if (!head->right || (head->right && head->right->val <= 0))
  103. {
  104. head = head->left;
  105. head->val = head->val - 1;
  106. ans = (ans + (1ll << i));
  107. }
  108. else
  109. {
  110. head = head->right;
  111. head->val = head->val - 1;
  112. }
  113. }
  114. }
  115. return ans;
  116. }
  117.  
  118. void mainSolve()
  119. {
  120. get(n);
  121. getvec(a, n);
  122. getvec(b, n);
  123. Node *head = new Node();
  124. for (int x : b)
  125. {
  126. add(x, head);
  127. }
  128. vl ans;
  129. for (int x : a)
  130. {
  131. ll curr = query(x, head);
  132. ans.pb(curr);
  133. }
  134. printv(ans);
  135. }
  136.  
  137. int main()
  138. {
  139. fio;
  140. #ifndef ONLINE_JUDGE
  141. freopen("input.txt", "r", stdin);
  142. freopen("output.txt", "w", stdout);
  143. #endif
  144. //get(t);
  145. ll t = 1;
  146. while (t--)
  147. {
  148. mainSolve();
  149. }
  150. return 0;
  151. }
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement