SHARE
TWEET

Untitled

a guest Jul 14th, 2015 269 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define pii pair<int, int>
  4.  
  5. #define pb push_back
  6. #define mp make_pair
  7.  
  8. #define f first
  9. #define s second
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14.  
  15. const int MAXN = (int) 3e6 + 7;
  16. const int INF = (int) 1e9 + 7;
  17.  
  18. int n;
  19. int a[MAXN];
  20.  
  21. ll moves[MAXN];
  22.  
  23. int used[MAXN];
  24. int timer;
  25.  
  26. int cnt[MAXN];
  27. int mn[MAXN];
  28.  
  29. int main() {
  30.   #ifdef LOCAL
  31.   freopen("in", "r", stdin);
  32.   #endif
  33.  
  34.   scanf("%d", &n);
  35.   for (int i = 1; i <= n; i++) {
  36.     ++timer;
  37.     scanf("%d", &a[i]);
  38.     vector<pii> all;
  39.     for (int it = 0, x = a[i]; x > 0; it++, x >>= 1) {
  40.       all.pb(mp(x, it));
  41.       for (int it2 = it + 1, y = x * 2; y <= 300000; y <<= 1, it2++) {
  42.         all.pb(mp(y, it2));
  43.       }
  44.     }
  45.     timer++;
  46.     for (auto it : all) mn[it.f] = INF;
  47.     for (auto it : all) {
  48.       mn[it.f] = min(mn[it.f], it.s);
  49.     }
  50.     for (auto it : all) {
  51.       if (used[it.f] != timer)
  52.         cnt[it.f]++,
  53.         moves[it.f] += mn[it.f];
  54.       used[it.f] = timer;
  55.     }
  56.   }
  57.   ll ans = 1e11;
  58.   for (int i = 1; i <= 300000; i++) {
  59.     if (cnt[i] == n) {
  60.       ans = min(ans, moves[i]);
  61.     }
  62.   }
  63.   cout << ans;
  64.   return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top