CF - Cellular Network

C++

Solution 1 - Binary Search on a Sorted Array

#include <bits/stdc++.h>
using namespace std;

// returns the first index in the array that is >= value, or arr.size() if no such index exists
int firstAtLeast(const vector<int>& arr, int value) {
	int lo = 0, hi = arr.size();
	while (lo < hi) {
		int mid = (lo+hi)/2;
		if (arr[mid] >= value) hi = mid;
		else lo = mid+1;

Solution 2 - Two Pointers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector<int> vi;

#define mp make_pair
#define pb push_back

Solution 3 - Using a Set

We use the set $\texttt{towers}$ to store the coordinates of the cellular towers. For each city, we want to find the closest tower and calculate the distance. The minimal $r$ will be the maximum of all these distances. To find the closest tower to a certain city, we check the towers to the left and right and determine which one is closer.

For each city, we use lower_bound to find the closest tower to the right of the city. If this tower is found, calculate the distance between this tower and the city. If the tower is not at the beginning of the set, the previous tower in the set will be the tower to the left of the city. Define $\texttt{dist}$ to be the minimum of the distance to the tower on the right and the distance to the tower on the left. Then, set $r$ to be the maximum of itself and $\texttt{dist}$.

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	int cities[n];