fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e5)+7;
  14. const int LOG = 60;
  15.  
  16. int n;
  17. ll k , a[maxN] , b[maxN];
  18.  
  19.  
  20. struct node{
  21.     int nxt[2] , cnt;
  22.  
  23.     node(){
  24.         cnt = 0;
  25.         nxt[0] = nxt[1] = -1;
  26.     }
  27. };
  28.  
  29. vector<node> trie;
  30.  
  31. void ins(ll x){
  32.     int id = 0;
  33.     for (int i = LOG ; i >= 0 ; i--){
  34.         int c = ((x>>i)&1);
  35.         if (trie[id].nxt[c] == -1){
  36.             trie.push_back(node());
  37.             trie[id].nxt[c] = sz(trie) - 1;
  38.         }
  39.         id = trie[id].nxt[c];
  40.         trie[id].cnt++;
  41.     }
  42. }
  43.  
  44. int nxt_id(int id , int c){
  45.     if (id == -1) return -1;
  46.     return trie[id].nxt[c];
  47. }
  48.  
  49. int get_cnt(int id){
  50.     if (id == -1) return 0;
  51.     return trie[id].cnt;
  52. }
  53.  
  54. int get(ll x , ll y){
  55.     int id = 0 , ans = 0;
  56.     for (int i = LOG ; i >= 0 ; i--){
  57.         int c = (((x ^ y)>>i)&1);
  58.         if ((y>>i)&1){
  59.             ans += get_cnt(nxt_id(id , c ^ 1));
  60.         }
  61.         id = nxt_id(id , c);
  62.     }
  63.     ans += get_cnt(id);
  64.     return ans;
  65. }
  66.  
  67. bool check(ll x){
  68.     ll ans = 0;
  69.     for (int i = 1 ; i <= n ; i++){
  70.         ans += 1ll * get(b[i] , x);
  71.     }
  72.     return ans >= k;
  73. }
  74.  
  75. int id[maxN];
  76.  
  77. void solve(){
  78.     cin >> n >> k;
  79.     trie.push_back(node());
  80.     for (int i = 1 ; i <= n ; i++){
  81.         cin >> a[i];
  82.         ins(a[i]);
  83.     }
  84.     for (int i = 1 ; i <= n ; i++){
  85.         cin >> b[i];
  86.     }
  87.     for (int i = 1 ; i <= n ; i++) id[i] = 0;
  88.     ll ans = 0;
  89.     for (int i = LOG ; i >= 0 ; i--){
  90.         ll num = 0;
  91.         for (int j = 1 ; j <= n ; j++){
  92.             int c = (b[j]>>i)&1;
  93.             num += 1ll * get_cnt(nxt_id(id[j] , c));
  94.         }
  95.         if (num >= k){
  96.             for (int j = 1 ; j <= n ; j++){
  97.                 int c = (b[j]>>i)&1;
  98.                 id[j] = nxt_id(id[j] , c);
  99.             }
  100.         }
  101.         else{
  102.             k -= num;
  103.             for (int j = 1 ; j <= n ; j++){
  104.                 int c = (b[j]>>i)&1;
  105.                 id[j] = nxt_id(id[j] , c ^ 1);
  106.             }
  107.             ans |= (1ll<<i);
  108.         }
  109.     }
  110.     cout << ans << "\n";
  111.     trie.clear();
  112. }
  113.  
  114. #define name "I"
  115.  
  116. int main(){
  117.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  118.     if (fopen(name".INP" , "r")){
  119.         freopen(name".INP" , "r" , stdin);
  120.         freopen(name".OUT" , "w" , stdout);
  121.     }
  122.     int t = 1; cin >> t;
  123.     while (t--) solve();
  124.     return 0;
  125. }
  126.  
  127.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qedvs3
language:
C++ (gcc 8.3)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!