fork download
copy 
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <utility>
  6. #include <set>
  7. #include <queue>
  8. #define ll long long int
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define FOR(i,a,b) for(int i=a;i<b;i++)
  13. #define FORR(i,a,b) for(int i = a;i>b;i--)
  14. #define ri(x) scanf("%d", &x)
  15. #define rl(x) scanf("%lld", &x)
  16. using namespace std;
  17.  
  18. typedef vector<ll> vl;
  19. typedef vector<int> vi;
  20. ll n;
  21. ll f2(ll k){
  22.     ll g = (n-k)/10;
  23.     ll sum = g;
  24.     ll r = (n- g);
  25.     while((r - ((r - k)/10)) >= k){
  26.         r = r - ((r-k)/10);
  27.         sum += ((r-k)/10);
  28.     }
  29.     return sum;
  30. }
  31.  
  32. bool f(ll k){
  33.     ll morn = n/(2*k);
  34.     ll s = f2(k);
  35.     if(k*morn + n - s <= n) return true;
  36.     return false;
  37. }
  38.  
  39. ll bsearch(ll lo, ll hi){
  40.     while(lo<=hi){
  41.         ll mi = (lo+hi+1)/2;
  42.         if(!f(mi-1) && f(mi)) return mi;
  43.         if(f(mi) && f(mi-1) ) hi = mi-1;
  44.         else lo = mi +1;
  45.     }
  46.     return lo;
  47. }
  48.  
  49. int main() {
  50.     rl(n);
  51.     ll ans = bsearch(1, n);
  52.     printf("%lld\n", ans);
  53.     printf("%d", f(3));
  54.     return 0;
  55. }
  56.  
Time limit exceeded #stdin #stdout 5s 4544KB
comments (?)
stdin
copy 
68
stdout
copy 
Standard output is empty
https://ideone.com/6QzJKy
language:
C++14 (gcc 8.3)
created:
5 years 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!