Why is the STL failing?

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	awoo	158
4	cry	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	maroonrk	152

Here is an AC submission:

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Here is an WA submission:

#include <bits/stdc++.h>
#define int unsigned long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>

using namespace std;

int mysqrt(int x) {
    int l = 0, r = x, ans = 0;
    while (l <= r) {
        int mid = l + (r-l)/2;
        if ((__uint128_t)mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

void solve(){
    int k;
    cin >> k;
    unsigned long long l=0,r=ULLONG_MAX;
    while(l<=r){
        int mid = l+(r-l)/2;
        int take = mysqrt(mid);
        int num = mid-take;
        if(num < k){
           l = mid+1;
        } else{
            r = mid - 1;
        }
    }
    cout << r+1 << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

The only difference is a custom sqrt function. This was my worse contest ever because of this. Wasted like 40 mins trying figure this out and needed like 1 more min to solve C. Someone please explain because this is so weird and frustrating.

Comments (7)

Write comment?

de3d_inside

103 minutes ago, # |

Man both your codes are same :)

→ Reply

101 minute(s) ago, # |

I believe B was too tight on constraints https://codeforces.me/contest/2020/submission/283621067 Here's my solution you can check. Make hi = 2*k and it would work.

Negationist

89 minutes ago, # ^ |

Still doesn't work: https://codeforces.me/contest/2020/submission/283671671

1guptagaurav

100 minutes ago, # |

I guess you pasted same codes

74 minutes ago, # ^ |

oh shoot lol youre right, either way i got a good answer

Nyemot

90 minutes ago, # |

You pasted same code.
I found your submissions.
seems like you didn't consider floating precision error.
here's mine with STL 283569591

83 minutes ago, # ^ |

Ok thanks. I will do some research into floating point imprecision and how to avoid it.

Negationist's blog