Here is an AC submission:
AC
#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:
WA
#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.
