Guest User

K - Counting Good Teams 2

a guest
Aug 29th, 2017
291
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define mp make_pair
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11. typedef pair<int ,int> ii;
  12. typedef vector<int> vi;
  13.  
  14. vi nums;
  15. int cnt[1 << 11][1 << 11];
  16.  
  17. bool cmp(const int &a, const int &b) {
  18.     int pa = __builtin_popcount(a);
  19.     int pb = __builtin_popcount(b);
  20.     if(pa == pb) {
  21.         return a < b;
  22.     }else {
  23.         return pa < pb;
  24.     }
  25. }
  26.  
  27. int main() {
  28.     ll n, m;
  29.     cin >> n >> m;
  30.     for(int i = 0; i < n; i++) {
  31.         int cur;
  32.         cin >> cur;
  33.         nums.pb(cur);
  34.     }
  35.     sort(nums.begin(), nums.end(), cmp);
  36.    
  37.     int h1 = m/2;
  38.     int h2 = m - h1;
  39.     ll ans = 0;
  40.     for(int i = 0; i < n; i++) {
  41.         int h1bit = 0;
  42.         int h2bit = 0;
  43.         int curn = nums[i];
  44.         ll curans = 0;
  45.         for(int j = 0; j < h1; j++) {
  46.             h1bit *= 2;
  47.             h1bit += curn&1;
  48.             curn = curn >> 1;
  49.         }
  50.         for(int j = 0; j < h2; j++) {
  51.             h2bit *= 2;
  52.             h2bit += curn&1;
  53.             curn = curn >> 1;
  54.         }
  55.  
  56.         for(int j = h2bit; j; j = ((j - 1)&h2bit)) {
  57.             curans += cnt[h1bit][j];
  58.         }
  59.  
  60.         curans += cnt[h1bit][0];
  61.         ans += curans;
  62.  
  63.         int h1bitneg = (~h1bit)&((1 << h1)-1);
  64.  
  65.         for(int j = h1bitneg; j; j = ((j - 1)&h1bitneg)) {
  66.             cnt[j | h1bit][h2bit]++;
  67.         }
  68.         cnt[h1bit][h2bit]++;
  69.     }
  70.     cout << (n*(n-1))/2 - ans << endl;
  71.     return 0;
  72. }
RAW Paste Data