Guest User

Untitled

a guest
Jul 5th, 2019
628
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long double ld;
  5. typedef long long ll;
  6. int n;
  7. const int maxN = 2 * (int)1e5 + 100;
  8. const int LIM = 62;
  9. ll a[maxN];
  10. ll dp[LIM + 10][maxN];
  11. const ll one = 1;
  12. const ll INF = (one << LIM);
  13. int bit(int x) {
  14. int bt = 0;
  15. for (int i = 0; i <= 20; i++) {
  16. if (x & (1 << i)) bt++;
  17. }
  18. return bt;
  19. }
  20. int solve_stupid() {
  21. int ans = (int)1e9;
  22. for (int i = 0; i <= 1000000; i++) {
  23. int cur = 0;
  24. for (int j = 1; j <= n; j++) {
  25. cur += bit(a[j] + i);
  26. }
  27. ans = min(ans, cur);
  28. }
  29. return ans;
  30. }
  31. int main() {
  32. ios_base::sync_with_stdio(false);
  33. cin.tie(nullptr);
  34. //freopen("input.txt", "r", stdin);
  35. srand(time(0));
  36. cin >> n;
  37. //n = rand() % 1000 + 10;
  38. ll mx = 0;
  39. for (int i = 1; i <= n; i++) {
  40. cin >> a[i];
  41. //a[i] = rand() % 1242 + 10;
  42. mx = max(mx, a[i]);
  43. }
  44. for (int i = 1; i <= n; i++) {
  45. a[i] = mx - a[i];
  46. }
  47. for (int i = 0; i <= LIM + 4; i++) {
  48. for (int j = 0; j <= n; j++) {
  49. dp[i][j] = INF;
  50. }
  51. }
  52. dp[0][0] = 0;
  53. vector < int > f;
  54. for (int i = 1; i <= n; i++) f.push_back(i);
  55. for (int bit = 0; bit <= LIM; bit++) {
  56. if (bit != 0) {
  57. vector<int> nf;
  58. for (int v : f) {
  59. if (!(a[v] & (one << (bit - 1)))) nf.push_back(v);
  60. }
  61. for (int v : f) {
  62. if (a[v] & (one << (bit - 1))) nf.push_back(v);
  63. }
  64. f = nf;
  65. }
  66. vector < int > prefZeroes(n + 1);
  67. vector < int > prefOnes(n + 1);
  68. prefZeroes[0] = prefOnes[0] = 0;
  69. for (int i = 1; i <= n; i++) {
  70. prefOnes[i] = prefOnes[i - 1];
  71. prefZeroes[i] = prefZeroes[i - 1];
  72. if (a[f[i - 1]] & (one << bit)) prefOnes[i]++;
  73. else prefZeroes[i]++;
  74. }
  75. int total_zeroes = prefZeroes[n];
  76. int total_ones = prefOnes[n];
  77. assert(total_ones + total_zeroes == n);
  78. for (int suf_take = 0; suf_take <= n; suf_take++) {
  79. for (int bt = 0; bt < 2; bt++) {
  80. if (dp[bit][suf_take] == INF) continue;
  81. if (bt == 0) {
  82. int numOnes = (total_zeroes - prefZeroes[n - suf_take]) + prefOnes[n - suf_take];
  83. int carry_ones = (total_ones - prefOnes[n - suf_take]);
  84. dp[bit + 1][carry_ones] = min(dp[bit + 1][carry_ones], dp[bit][suf_take] + numOnes);
  85. }
  86. else {
  87. int numOnes = (total_ones - prefOnes[n - suf_take]) + prefZeroes[n - suf_take];
  88. int carry_ones = n - prefZeroes[n - suf_take];
  89. dp[bit + 1][carry_ones] = min(dp[bit + 1][carry_ones], dp[bit][suf_take] + numOnes);
  90. }
  91. }
  92. }
  93. }
  94. ll ans = dp[LIM + 1][0];
  95. //assert(ans == solve_stupid());
  96. cout << ans;
  97. return 0;
  98. }
RAW Paste Data