fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<long long, long long> pll;
  5.  
  6. #define fi first
  7. #define sec second
  8.  
  9. const int LN = 30;
  10.  
  11. int n, k, p, u, v;
  12. vector<int> a;
  13. long long inv_cnt[LN][2];
  14. vector<pll> high_bit, low_bit;
  15.  
  16. void rec(vector<int> &a, int bit) {
  17.   if (!a.size() || bit < 0) return;
  18.   int zero = 0, one = 0;
  19.   vector<int> unset_bit, set_bit;
  20.   for(int x : a) {
  21.     if (x & (1 << bit)) {
  22.       one += 1;
  23.       // if the bit is set in X, then inversion will be present as before
  24.       // (0 < 1), but later it will be (0 ^ 1) > (1 ^ 1).
  25.       inv_cnt[bit][1] += zero;
  26.       set_bit.push_back(x);
  27.     }
  28.     else {
  29.       zero += 1;
  30.       // if the bit is unset in X, then inversion will be present as before
  31.       // (1 > 0), but later it will be (1 ^ 1) < (0 ^ 1).
  32.       inv_cnt[bit][0] += one;
  33.       unset_bit.push_back(x);
  34.     }
  35.   }
  36.   rec(set_bit, bit - 1);
  37.   rec(unset_bit, bit - 1);
  38. }
  39.  
  40. long long get(pll valid_pair) {
  41.   // 2 - pointers approach.
  42.   // Given two arrays: U and V and we need to find how many valid pairs
  43.   // (inversion_count, number) are less than given valid pair.
  44.   long long res = 0;
  45.   int p2 = low_bit.size() - 1;
  46.   for(int p1 = 0; p1 < high_bit.size(); ++p1) {
  47.     while(p2 >= 0) {
  48.       // pair: {number of inversions, number X considered}
  49.       pll y = {high_bit[p1].fi + low_bit[p2].fi,
  50.                (high_bit[p1].sec << u) + low_bit[p2].sec};
  51.       if (y <= valid_pair) {
  52.         break;
  53.       }
  54.       p2 -= 1;
  55.     }
  56.     res += p2 + 1;// 0-based indexing of array. Added 1 to get the actual count.
  57.   }
  58.   return res;
  59. }
  60.  
  61. int main() {
  62.   ios_base::sync_with_stdio(false);
  63.   int t;
  64.   cin >> t;
  65.   while(t--) {
  66.     // Input.
  67.     cin >> n >> k >> p;
  68.     a.resize(n);
  69.     for(int i = 0; i < n; ++i) {
  70.       cin >> a[i];
  71.     }
  72.     // Clear.
  73.     for(int i = 0; i < k; ++i) {
  74.       inv_cnt[i][0] = 0;
  75.       inv_cnt[i][1] = 0;
  76.     }
  77.     // Pre-computation.
  78.     rec(a, k - 1);
  79.     // Meet-in-the-middle pre-computation.
  80.     low_bit.clear();
  81.     high_bit.clear();
  82.     u = k / 2, v = k - u;
  83.     for(int i = 0; i < (1 << u); ++i) {
  84.       long long inv = 0;
  85.       for(int j = 0; j < u; ++j) {
  86.         inv += inv_cnt[j][(i >> j) & 1];
  87.       }
  88.       low_bit.push_back({inv, i});
  89.     }
  90.     for(int i = 0; i < (1 << v); ++i) {
  91.       long long inv = 0;
  92.       for(int j = 0; j < v; ++j) {
  93.         inv += inv_cnt[j + u][(i >> j) & 1];
  94.       }
  95.       high_bit.push_back({inv, i});
  96.     }
  97.     sort(low_bit.begin(), low_bit.end());
  98.     sort(high_bit.begin(), high_bit.end());
  99.     // Binary search 1: Find number of inversion in the P^th number.
  100.     long long l1 = 0, h1 = (long long)n * (n - 1) / 2;
  101.     while(l1 <= h1) {
  102.       long long m = (l1 + h1) / 2;
  103.       // Find count of numbers such that number of inversions is less than "m".
  104.       // The second number is a large number which doesn't matter to us.
  105.       // It is written just to avoid writing 2 check functions for binary
  106.       // search. Will become clear after seeing the second binary search.
  107.       long long res = get({m, INT_MAX});
  108.       if (res >= p) {
  109.         h1 = m - 1;
  110.       }
  111.       else {
  112.         l1 = m + 1;
  113.       }
  114.     }
  115.     long long l2 = 0, h2 = (1 << k) - 1;
  116.     while(l2 <= h2) {
  117.       long long m = (l2 + h2) / 2;
  118.       // Find count of numbers such that number of inversions are less than or
  119.       // equal to "l1" and the numbers considered are less than "m". This means
  120.       // if two numbers have same inversion count, thet are sorted by magnitude
  121.       // of the number.
  122.       long long res = get({l1, m});
  123.       if (res >= p) {
  124.         h2 = m - 1;
  125.       }
  126.       else {
  127.         l2 = m + 1;
  128.       }
  129.     }
  130.     cout << l2 << "\n";
  131.   }
  132.   return 0;
  133. }
Success #stdin #stdout 0s 4336KB
comments ()
stdin
copy 
3
4 3 5
2 0 3 7
2 2 1
2 0
6 3 2
7 5 3 4 1 2
stdout
copy 
4
2
5
https://ideone.com/cDh74I
language:
C++14 (gcc 8.3)
created:
6 years 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!