fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define sz(x) x.size()
  6. #define all(v) v.begin(), v.end()
  7. #define allr(v) v.rbegin(), v.rend()
  8. #define F first
  9. #define S second
  10.  
  11. int n;
  12.  
  13. int f(int val)
  14. {
  15.     int cnt = 0;
  16.     for (int i = 1; i <= n; ++i)
  17.         cnt += min(n, val / i);
  18.     return cnt;
  19. }
  20.  
  21. void solve()
  22. {
  23.     cin >> n;
  24.     int l = 0, h = n * n, target = n * n / 2 + 1;
  25.     int ans = h;
  26.     while (l <= h)
  27.     {
  28.         int mid = l + (h - l) / 2;
  29.         if (f(mid) >= target)
  30.             h = mid - 1, ans = mid;
  31.         else
  32.             l = mid + 1;
  33.     }
  34.     cout << ans;
  35. }
  36.  
  37. signed main()
  38. {
  39.     ios_base::sync_with_stdio(0), cin.tie(0);
  40.     int tc = 1;
  41.     // cin >> tc;
  42.     while (tc--)
  43.     {
  44.         solve();
  45.         if (tc)
  46.             cout << '\n';
  47.     }
  48.     return 0;
  49. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rMfpUR
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!