Advertisement
karupayun

tap17/k.cpp

Oct 22nd, 2017
169
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #define dprint(v) cerr << #v"=" << v << endl
  5.  
  6. using namespace std;
  7. #define MAXN 100000
  8. #define forr(i,a,b) for(int i=(a); i<(b); i++)
  9. #define forn(i,n) forr(i,0,n)
  10. #define pb push_back
  11. typedef long long ll;
  12.  
  13. int persona[MAXN];
  14.  
  15. int n, k, m, v;
  16. ll suma;
  17. #define INF 1000000
  18.  
  19. int lastbit0(ll v){
  20.     int rta = 1;
  21.     v /= 2;
  22.     while (v % 2){
  23.         rta++;
  24.         v /= 2;
  25.     }
  26.     return rta;
  27. }
  28.  
  29. vector <int> p; // Pares
  30. vector <int> im; // Impares
  31.  
  32. int main(){
  33.     cin >> n;
  34.     forn (i,n) {cin >> v;
  35.     if (v % 2){
  36.         im.pb(lastbit0(v));
  37.     }
  38.     else{
  39.         p.pb(lastbit0(v));
  40.     }
  41.    }
  42.     sort (im.begin(), im.end());
  43.     sort (p.begin(), p.end());
  44.    
  45.     m = im.size();
  46.     int mpares = p.size();
  47.  
  48.     int mini = INF;
  49.     if (mpares) mini = min (mini, p[0]);
  50.     if (m) mini = min (mini, im[0]);
  51.    
  52.     int rta = m+1;
  53.     if (mini <= m || !m) rta = m; // Lema: La respuesta es menor que m+1 sii existe un a[i] con un bit en 0 entre (1 y m)
  54.    
  55.     int aux = m;
  56.     int i = 0;
  57.     if (rta == m) // Si existe aplico el greedy
  58.         while (m){
  59.             if (im[i] < aux){
  60.                 aux -= im[i] + 1;
  61.                 i++;
  62.             }
  63.             else break;
  64.            
  65.         }
  66.     cout << rta - i << endl;
  67.  
  68.     return 0;  
  69. }
Advertisement
RAW Paste Data Copied
Advertisement