### arnav2004's blog

By arnav2004, history, 2 months ago,

I was solving this bugabooLink to the bugaboo.

Here's my code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const ll INF = 1e18;
const int MOD = 1e9+7;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int a,b,c;
cin>>a>>b>>c;
if(c==a){
cout<<1<<"\n";
continue;
}
if(c <= (a+b) / 2){
cout<<2<<"\n";
continue;
}
ll start = 1;
ll high = (1LL<<40);
ll mini = 0;
double te = 0;
while(start<=high){
ll mid = (start+high)/2;
ll sum = (1LL * mid * a) + (1LL*(mid-1)*b);
double avg = (0.0000+sum) / (0.0000+mid+mid-1);
if(avg>=c){
mini = mid;
start = mid+1;
}
else
high = mid-1;
}
te = (a+b)/2;
ll ans = 2;
for(ll mid = mini;mid<=mini+100;mid++){
ll sum = (1LL * mid * a) + (1LL*(mid-1)*b);
double avg = (0.0000+sum) / (0.0000+mid+mid-1);
if(abs(avg-c)<abs(te-c)){
te = avg;
ans = mid+mid-1;
}
}
cout<<ans<<"\n";
}
}


This code got AC in C++14 and WA in C++17(64). Is it this happening maybe because of some precision errors or is there any other reason?

• +6

By arnav2004, history, 2 months ago,

I was solving problem C of Educational Round 109 which was held yesterday.The link to the question.

Here is my code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INF = 1e9;
const int MOD = 1e9+7;
struct point{
int x,idx;
char dir;
};
int n,m;
int ans[300005];
bool cmp(point a,point b){
return a.x<b.x;
}
void helper(vector<point>&v){
sort(v.begin(),v.end(),cmp);
for(auto i:v)
cout<<i.dir<<endl;
deque<point>right,left;
for(int i = 0;i<v.size();i++){
if(v[i].dir=='R')
right.push_back(v[i]);
else{
if(!right.empty()){
point topmost = right.back();
right.pop_back();
int dist = (v[i].x - topmost.x)/2;
ans[v[i].idx] = dist;
ans[topmost.idx] = dist;
}
else
left.push_back(v[i]);
}
}
while(left.size()>=2){
point l = left.front();
left.pop_front();
point r = left.front();
left.pop_front();
int dist = l.x+(r.x-l.x)/ 2;
ans[l.idx] = dist;
ans[r.idx] = dist;
if(dist==6){
cout<<l.x<<" "<<r.x<<endl;
}
}
while(right.size()>=2){
point l = right.front();
right.pop_front();
point r = right.front();
right.pop_front();
int dist = m-(l.x+r.x) / 2;
ans[l.idx] = dist;
ans[r.idx] = dist;
}
if(!left.empty() && !right.empty()){
point l = left.front();
point r = right.front();
int dist = m+(l.x-r.x)/2;
ans[l.idx] = dist;
ans[r.idx] = dist;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>m;
vector<point>a(n);
vector<point>odd,even;
for(int i = 0;i<n;i++){
cin>>a[i].x;
a[i].idx = i;
if((a[i].x)&1)
odd.push_back(a[i]);
else
even.push_back(a[i]);
}
for(int i = 0;i<n;i++){
cin>>a[i].dir;
}
memset(ans,-1,sizeof ans);
helper(odd);
helper(even);
for(int i = 0;i<n;i++){
cout<<ans[a[i].idx]<<" ";
}
cout<<"\n";
}
}


I made a struct point which contains x(coordinate of point), idx(index of point) and dir(direction — L or R).

Now as you can see in my helper function I have sorted the vector according to their x coordinates. But after sorting the points when I print some arbitrary points dir(direction) the output comes out to be hexadecimal(I think) like this : 000d 0a00 0d0a 000d 0a00 0d0a 3520 370d.

Can anyone tell me why is this happening and how to fix this?

• 0

By arnav2004, history, 5 months ago,

I was recently solving this question using binary search(https://codeforces.com/problemset/problem/1201/C). I came to know about my mistake as my formula for calculating mid was low+(high-low)/2 but instead when I use low+(high-low+1)/2 I get AC.

My questions is when(and why) do we use low+(high-low+1)/2. I tried to google it and could not find any link which answers my question.