c++ - Using binary search to find k-th largest number in n*m multiplication table -

so, trying solve problem: http://codeforces.com/contest/448/problem/d

bizon champion isn't charming, smart.

while of learning multiplication table, bizon champion had fun in own manner. bizon champion painted n × m multiplication table, element on intersection of i-th row , j-th column equals i·j (the rows , columns of table numbered starting 1). asked: number in table k-th largest number? bizon champion answered correctly , immediately. can repeat success?

consider given multiplication table. if write out n·m numbers table in non-decreasing order, k-th number write out called k-th largest number.

input single line contains integers n, m , k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).

output print k-th largest number in n × m multiplication table.

what did was, applied binary search 1 n*m looking number has k elements less it. this, made following code:

using namespace std; #define ll long long #define pb push_back #define mp make_pair ll n,m; int f (int val); int min (int a, int b); int main (void) {     int k;     cin>>n>>m>>k;     int ind = k;     ll low = 1ll;     ll high = n*m;     int ans;     while (low <= high)     {         ll mid = low + (high-low)/2;         if (f(mid) == k)             ans = mid;         else if (f(mid) < k)             low = mid+1;         else             high = mid-1;     }     cout<<ans<<"\n";     return 0;  }  int f (int val) {     int ret = 0;     ( int = 1; <= n; i++ )     {         ret = ret + min(val/i,m);     }     return ret; }  int min (int a, int b) {     if (a < b)         return a;     else         return b; } 

however, don't know why gives wrong answer on test cases:

input 2 2 2 output 2 

my output comes out 0

i learning binary search don't know going wrong implementation. appreciated.

ignoring fact binary search not fastest method, still want know why incorrect.

first clear want , f returning:

looking number has k elements less it.

no! looking smallest number has k elements less or equal it. , function f(x) returns count of elements less or equal x.

so when f(x) returns value small, know x must larger @ least 1, low=mid+1 correct. when f(x) returns value large, x might perfect (might element appearing several times in table). conversely, when f(x) returns right number, x might still big (x might value appears 0 times in table).

so when f(x) not small, best can high=mid not high=mid-1

while (low < high) {     ll mid = low + (high-low)/2;     if (f(mid) < k)         low = mid+1;     else         high = mid; } 

notice low never gets > high, stop when equal, , don't try catch ans along way. instead @ end low==high==answer

the contest says 1 second time limit. on computer, code correction solves max size problem in under second. i'm not sure judging computer fast.

edit: int small max size of problem, can't return int f:
n, m, , each fit in 32 bits, input , output of f() k, ret, low , high need hold integers 2.5e11