Help needed in Wormholes (ZCO12002)!

general
,
1

Problem: Wormholes

My Solution: 70/100 Partial AC

#include <bits/stdc++.h>

using namespace std;

#define scin(a) scanf("%d",&(a))
#define prin(a) printf("%d",(a))

int main() {
    int N, X, Y;
    scin(N);
    scin(X);
    scin(Y);
    vector<int> V(X), W(Y);
    vector<pair<int, int>> cont(N);
    for (int i = 0; i < N; i++)
        scanf("%d %d", &cont[i].first, &cont[i].second);
    for (int i = 0; i < X; i++)
        scin(V[i]);
    for (int i = 0; i < Y; i++)
        scin(W[i]);
    sort(V.begin(), V.end());
    sort(W.begin(), W.end());
    int mn = INT_MAX, start, end, v, w;
    for (auto i:cont) {
        start = i.first;
        end = i.second;
        if (lower_bound(W.begin(), W.end(), end) != W.end())
            w = *lower_bound(W.begin(), W.end(), end);
        auto vIter = upper_bound(V.begin(), V.end(), start);
        if (vIter == V.end() || vIter == V.begin())
            continue;
        else
            --vIter;
        v = *vIter;
        mn = min(mn, abs(w - v) + 1);
    }
    prin(mn);
    return 0;
}

My approach:

I sort the entering and exiting wormholes according to time.
Then for each contest, I check for the minimum time possible. I fail in two sub-tasks, but I can’t figure out why!

Thanks in advance!

Arnav

2

Try this:

2 2 1
5 10
11 12
5 11
12
1 Like
3

I agree with the comment above

4

You could comment such things instead of answering: “I agree with the comment above”, “very interesting” etc.

5

I understood what you were wanting to point out, but how could I fix it?

6

You’ll have to write your own binary search. Once you do that, run your code on this:

2 3 1
5 10
11 12
5 11 12
11
7

There’s a certain minimum karma one needs to have before being able to comment.

1 Like