Olympiad task " Small denominators"

Time limit: 2 seconds.
Memory limit: 512 MB.

Condition:

Two fractions are given a/b c/d with non-negative integer numerators and positive integer denominators, and some positive integer N is selected. Consider all irreducible fractions e/f with positive integer numerators and denominators not exceeding N, lying between these two fractions: a/b e/f c/d . Write them in the final sequence in the order ascending first, denominators, numerators and then: roll e1/f1 will this list sooner e2/f2 , or if f1 f2, or if f1 = f2 and e1 e2. Your goal is to output the first n fractions in this sequence (or the entire sequence if there are less than n fractions in it).

Input data format:

The first line contains six integers a, b, c, d, N, n - these two fractions, the restriction the numerator and denominator and the number of decimals that you want to plot (0 6 a 6 1018 , 1 b, c, d, N n a b c d.

Output format:

In the first line, output an integer n' - the number of fractions that you will output. In the following n' lines, print the fractions themselves in the correct order: in the i line, there must be integers ei and fi , separated by a space - mutually prime numerator and denominator of the i th fraction (1 ei , fi n' must either be n, or lie between 0 and n-1 and equal the number of irreducible fractions between a b and c d , whose numerators and denominators are positive integers and do not exceed N.

Examples:

Input: 0 1 1 1 5 10

Output:

9
1 2
1 3
2 3
1 4
3 4
1 5
2 5
3 5
4 5

Input: 55 34 68 42 90 1

Output:

1
89 55

Input: 49 33 45 30 50 239

Output:

0

My solution

I used Дерево Штерна-Броко to generate fractions.

For some reason, on most tests it gives Wrong Answer, on some Time Limit.

#include <iostream>
#include <set>

using namespace std;

class fraction {
public:
    long long numerator, denominator;

    fraction() : numerator(0), denominator(0) {}

    fraction(long long numerator, long long denominator) : numerator(numerator), denominator(denominator) {}

    bool operator==(const fraction & fr) {
        return numerator == fr.numerator && denominator == fr.denominator;
    }

    bool operator!=(const fraction & fr) {
        return numerator != fr.numerator || denominator != fr.denominator;
    }
};

bool compare(const fraction& fr1, const fraction& fr2) { // для set
    if (fr1.denominator != fr2.denominator)
        return fr1.denominator < fr2.denominator;
    return fr1.numerator < fr2.numerator;
}

bool operator>(const fraction& fr1, const fraction& fr2) {
    if (fr1.denominator != fr2.denominator)
        return (double)fr1.numerator * fr2.denominator > (double)fr2.numerator * fr1.denominator;
    return fr1.numerator > fr2.numerator;
}

bool operator<(const fraction& fr1, const fraction& fr2) {
    if (fr1.denominator != fr2.denominator)
        return (double)fr1.numerator * fr2.denominator < (double)fr2.numerator* fr1.denominator;
    return fr1.numerator < fr2.numerator;
}

ostream& operator<<(ostream& str, const fraction& fr) {
    str << fr.numerator << ' ' << fr.denominator;
    return str;
}

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

int main() {

    long long a, b, c, d, N; int n;
    cin >> a >> b >> c >> d >> N >> n;

    {
        long long gcd1 = gcd(a, b), gcd2 = gcd(c, d);
        a /= gcd1, b /= gcd1;
        c /= gcd2, d /= gcd2;
    }

    set<fraction, decltype(&compare)> fractionSet(&compare);

    // два массива для генерации дерева
    fraction* arr1 = new fraction[262144];
    fraction* arr2 = new fraction[262144];

    int len1 = 3, i2 = 0; // индексы 1 и 2 показывают отношение к arr1 и arr2

    arr1[0] = fraction(0, 1), arr1[1] = fraction(1, 1), arr1[2] = fraction(1, 0);

    {
        // по окончании этого блока в arr1 остаётся две или больше дробей, причём первая дробь минимальна и больше a/b, вторая максимальна и меньше c/d, и все дроби между ними правильно сгенерированы
        fraction sample1 = fraction(a, b), sample2 = fraction(c, d);
    label:
        if (sample1 > arr1[1]) {
            arr1[0] = arr1[1];
            arr1[1] = fraction(arr1[0].numerator + arr1[2].numerator, arr1[0].denominator + arr1[2].denominator);
            goto label;
        }
        if (sample2 < arr1[len1-2]) {
            arr1[len1-1] = arr1[len1-2];
            arr1[len1-2] = fraction(arr1[len1-3].numerator + arr1[len1-1].numerator, arr1[len1-3].denominator + arr1[len1-1].denominator);
            goto label;
        }
        if (arr1[0] != sample1)
            if (arr1[1] != sample1)
                while (true) {
                    fraction fr = fraction(arr1[0].numerator + arr1[1].numerator, arr1[0].denominator + arr1[1].denominator);
                    if (fr.numerator > N || fr.denominator > N) {
                        len1--;
                        for (int i = 0; i < len1; i++)
                            arr1[i] = arr1[i+1];
                        break;
                    }
                    if (fr < sample1)
                        arr1[0] = fr;
                    else if (fr > sample1) {
                        for (int i = len1; i > 1; i--)
                            arr1[i] = arr1[i - 1];
                        len1++;
                        arr1[1] = fr;
                    } else {
                        arr1[0] = fr;
                        break;
                    }
                } else {
                    arr1[0] = arr1[1];
                    arr1[1] = arr1[2];
                    len1--;
                }
        int tmp = len1 - 2;
        if (arr1[tmp] != sample2) {
            while (true) {
                fraction fr = fraction(arr1[tmp].numerator + arr1[tmp+1].numerator, arr1[tmp].denominator + arr1[tmp+1].denominator);
                if (fr.numerator > N || fr.denominator > N) {
                    len1--;
                    break;
                }
                if (fr > sample2)
                    arr1[tmp + 1] = fr;
                else if (fr < sample2) {
                    arr1[len1] = arr1[len1 - 1];
                    len1++;
                    arr1[++tmp] = fr;
                } else {
                    arr1[++tmp] = fr;
                    break;
                }
            }
        } else
            len1--;
    }

    if (len1 < 2) {
        cout << 0 << endl;
        exit(0);
    }
    /*
        indexForRemove убирает дроби, после генерации которых получится дробь с числителем или знаменателем больше, чем N.
        Например, при N = 5 в последовательности 1/2 2/3 1/1 он уберёт только первую дробь.
        Возможно, не самое лучшее решение по производительности.
    */
    for (int i = 0, prevLen = 0, indexForRemove = 0;; i++) {
        for (int i1 = 0;; i1++) {
            arr2[i2] = arr1[i1];
            i2++;
            if (i1 + 1 == len1)
                break;
            long long numerator = arr1[i1].numerator + arr1[i1+1].numerator;
            if (numerator > N) {
                if (indexForRemove == i2 - 1)
                    indexForRemove++;
                continue;
            }
            long long denominator = arr1[i1].denominator + arr1[i1+1].denominator;
            if (denominator > N) {
                if (indexForRemove == i2 - 1)
                    indexForRemove++;
                continue;
            }
            fraction fr = fraction(numerator, denominator);
            arr2[i2] = fr;
            fractionSet.insert(fr);
            i2++;
        }
        if (indexForRemove != 0)
            memcpy(arr2, arr2 + indexForRemove, i2 -= indexForRemove);
        if (i2 < 2)
            break;
        fraction* tmp = arr1;
        arr1 = arr2;
        arr2 = tmp;
        len1 = i2;
        i2 = 0;
        prevLen = len1;
        indexForRemove = 0;
    }

    int limit = fractionSet.size() < n ? fractionSet.size() : n;

    cout << limit;
    set<fraction, decltype(&compare)>::iterator it = fractionSet.begin();
    for (int i = 0; i < limit; i++, it++)
        cout << '\n' << *it;
    cout << endl;
}

Here is a variant with brute force fractions. Almost all the tests are again WA, some TL, however, the correct answers have become more)
Am I missing something?

int main() {

    long long a, b, c, d, N; int n;
    cin >> a >> b >> c >> d >> N >> n;

    long long* r = new long long[400'000];
    int pos = 0, i = a + 1, j = b;
    double f = (double)a / b, s = (double)c / d;

    while (n && j <= N) {
        int lim = min(N + 1, (long long)ceil(s * j));
        while (i < lim) {
            if (gcd(i, j) == 1) {
                r[pos++] = i;
                r[pos++] = j;
                if (--n == 0)
                    break;
            }
            i++;
        }
        i = ceil(f * ++j);
    }

    cout << pos / 2 << '\n';
    for (int i = 0; i < pos; i++) {
        cout << r[i] << ' ';
        cout << r[++i] << '\n';
    }
}