arnav2004's blog

By arnav2004, history, 2 months ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By arnav2004, history, 2 months ago, In English

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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By arnav2004, history, 5 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it