First of all here is the link to the problem:
(
http://codeforces.com/contest/448/problem/D)
Now I'll post my last 2 submissions because I don't understand something about them:
[Accepted submission]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
#include <bits/stdc++.h>
#define fl(n) for(int i = 0; i < n; i++)
#define ll long long
#define nl endl
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define EPS 1e-9
#define INF 1e9
using namespace std;
ll binsearch(ll n, ll m, ll k){
ll low = 1, high = n*m+1, mid;
while(low < high){
mid = (low+high) >> 1;
ll x = 0;
for(ll i = 1; i <= n; i++){
x+= min(m, (mid-1)/i);
}
//cout << low << " " << high << " " << mid << nl;
//if(x == k) return mid;
if(x >= k) high = mid;
else low = mid+1;
}
return low;
}
int main()
{
ll n, m, k;
cin >> n >> m >> k;
cout << (binsearch(n,m,k)-1);
return 0;
}
|
[Wrong answer submission]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
#include <bits/stdc++.h>
#define fl(n) for(int i = 0; i < n; i++)
#define ll long long
#define nl endl
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define EPS 1e-9
#define INF 1e9
using namespace std;
ll binsearch(ll n, ll m, ll k){
ll low = 1, high = n*m+1, mid;
while(low < high){
mid = (low+high) >> 1;
ll x = 0;
for(ll i = 1; i <= n; i++){
x+= min(m, (mid-1)/i);
}
//cout << low << " " << high << " " << mid << nl;
if(x == k) return mid;
if(x > k) high = mid;
else low = mid+1;
}
return low;
}
int main()
{
ll n, m, k;
cin >> n >> m >> k;
cout << (binsearch(n,m,k)-1);
return 0;
}
|
Basically the only difference between them was 1 line of code which is:
~~~~~
if(x == k) return mid;
~~~~~
^ in the WA submission
I commented that line of code above and changed the high value condition in the binsearch to
~~~~~
if(x >= k) high = mid;
~~~~~
Instead of just x > k, and it got accepted. and I am wondering why that made a difference?
Edit: Also I tested a part where I removed the -1 from this equation:
~~~~~
x+= min(m, (mid-1)/i);
~~~~~
But I had to remove the -1 from the cout
~~~~~
cout << (binsearch(n,m,k)-1);
~~~~~
It got accepted aswell xD, I thought the equation could only work with a -1 since we look for elements smaller than k? or am I missing something?
Thanks in advance!