fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define N "\n"
  4. using namespace std;
  5. ll count(ll x , ll radius){
  6.         ll left=0,right=radius,ans=0;
  7.         while(left<=right){
  8.                 ll mid=(left+right)/2;
  9.                 if(mid*mid<=radius*radius - x*x){
  10.                         ans=mid;
  11.                         left=mid+1;
  12.                 }
  13.                 else{
  14.                         right=mid-1;
  15.                 }
  16.         }
  17.         return ans;
  18. }
  19. bool bs(ll mid, ll k){
  20.         ll cnt=0;
  21.  
  22.         for(ll i=-mid;i<=mid;i++){
  23.                 ll mxY=count(i,mid);
  24.                 cnt+=(2*mxY)+1;
  25.         }
  26.         return cnt>=k;
  27. }
  28. int main()
  29. {
  30.         ios_base::sync_with_stdio(false);
  31.         cin.tie(NULL);
  32.         ll k;
  33.         cin >> k;
  34.  
  35.         ll lo=1,hi=1e5;
  36.         while(lo<=hi){
  37.                 ll mid=(lo+hi)/2;
  38.                 if(bs(mid,k)){
  39.                         hi=mid-1;
  40.                 }
  41.                 else{
  42.                         lo=mid+1;
  43.                 }
  44.         }
  45.         cout << lo << N;
  46.         return 0;
  47. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
13
stdout
copy 
2
https://ideone.com/R0Wmhr
language:
C++14 (gcc 8.3)
created:
3 days 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!