fork(1) download
copy 
  1. #include <iostream>
  2. #include <utility>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <numeric>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <iostream>
  9. #include <utility>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <numeric>
  13. #include <map>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <queue>
  17. #include <set>
  18. #include <stack>
  19. #include <fstream>
  20. #include <ext/pb_ds/assoc_container.hpp>
  21. #include <ext/pb_ds/tree_policy.hpp>
  22. #include <bitset>
  23. #include <sstream>
  24. #include <ext/rope>
  25. #include <ctime>
  26. #include <random>
  27. #include <cstdlib>
  28. #include <complex>
  29.  
  30. using namespace std;
  31. using namespace __gnu_pbds;
  32. using namespace __gnu_cxx;
  33.  
  34. /* clang-format off */
  35.  
  36. /* TYPES  */
  37. #define ll long long
  38. #define pii pair<int, int>
  39. #define pll pair<long long, long long>
  40. #define vi vector<int>
  41. #define vll vector<long long>
  42. #define vpii vector<pair<int, int>>
  43. #define vpii vector<pair<int, int>>
  44. #define vvpii vector<vector<pair<int, int>>>
  45. #define vpll vector<pair<long long, long long>>
  46. #define vvpll vector<vector<pair<long long, long long>>>
  47. #define vvi vector<vector<int>>
  48. #define vvll vector<vector<long long>>
  49. #define mii map<int, int>
  50. #define si set<int>
  51. #define sc set<char>
  52.  
  53.  
  54.  
  55. /* FUNCTIONS */
  56. #define feach(el, v) for(auto &el: v)
  57. #define rep(i, n) for(int i=0;i<n;i++)
  58. #define reprv(i, n) for(int i=n-1;i>=0;i--)
  59. #define reps(i, s, e) for(int i=s;i<e;i++)
  60. #define reprve(i, e, s) for(int i=e;i>=s;i--)
  61. #define repe(x, y) for (auto &x: y)
  62. #define repe2(x, a, y) for (auto &[x,a]: y)
  63.  
  64. typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> oSet;
  65.  
  66. bool check(vi &cnt, int k, int n) {
  67.     int tot = 0;
  68.     rep(i, cnt.size()) {
  69.         if (cnt[i] >= k) tot += k;
  70.         else tot += (cnt[i] + (k - cnt[i])/2);
  71.     }
  72.     return tot >= n;
  73. }
  74.  
  75. int main() {
  76.     int n, m, x; cin >> n >> m;
  77.     vi cacheCnt(n);
  78.     rep(i, m) cin >> x, cacheCnt[x - 1]++;
  79.  
  80.     int l = 0, r = 2 * m;
  81.     while (r - l > 1) {
  82.         int mid = (l + r) >> 1;
  83.         if (check(cacheCnt, mid, m)) r = mid;
  84.         else l = mid + 1;
  85.     }
  86.     if (check(cacheCnt, l, m)) cout << l;
  87.     else cout << r;
  88. }
Success #stdin #stdout 0s 5272KB
comments ()
stdin
copy 
3 5
1 1 3 1 1
stdout
copy 
3
https://ideone.com/6Cfxi6
language:
C++14 (gcc 8.3)
created:
278 days ago
visibility:
secret

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!