Competitive Programming Solutions

100971D - Laying Cables

07 Dec 2020 — Tags: sorting,implementation — URL

We’ll maintain two sets:

  1. ordx: Elements ordered by their position $x$.
  2. ordp: Elements ordered by their population $p$.

First note that to compute the parent of a city, we don’t need information about any city with less population.

So, we’ll compute the parent for each city (in increasing order of population) and remove such city from the set of candidates ordx. Since all cities with less population have been removed from ordx, the immediate neighbors of the current city in ordx will be our candidates. Pick the closest and biggest city.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using iii = tuple<int, int, int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ii> a(n);
    set<ii> ordx, ordp;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i].first >> a[i].second;
        ordx.emplace(a[i].first, i);
        ordp.emplace(a[i].second, i);
    }
    vi ans(n);
    for (auto [p, i] : ordp)
    {
        int x = a[i].first;
        auto it = ordx.lower_bound({x, 0});
        iii cur = {1e9, 0, -2};
        if (next(it) != end(ordx))
        {
            int j = next(it)->second;
            cur = min(cur, {abs(a[j].first - x), -a[j].second, j});
        }
        if (it != begin(ordx))
        {
            int j = prev(it)->second;
            cur = min(cur, {abs(a[j].first - x), -a[j].second, j});
        }
        ans[i] = get<2>(cur) + 1;
        ordx.erase(it);
    }
    for (auto x : ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

Related posts