Задача №3356. Минимальное покрытие

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stdio.h>
#include <sstream>
#include <iomanip>
using namespace std;
using ll = long long;
#define pshb(f) push_back(f)

void ct(vector <pair <int, int> >& v) {
    for (auto x : v) cout << x.first << ' ' << x.second << "  ";
    cout << '\n' << '\n';
}

void cp(pair <int, int> x) {
    cout << x.first << ' ' << x.second << '\n' << '\n';
}

bool cmp(pair <int, int> a, pair <int, int> b) {
    return a.first <b.first || a.first == b.first && a.second > b.second;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> m;
    vector <pair <int, int>> x;
    while (true) {
        int a, b;
        cin >> a >> b;
        if (a == 0 && b == 0) break;
        if (a < m && b > 0) x.push_back({ a,b });
    }
    sort(x.begin(), x.end(),cmp);
    int sz = (int)x.size();
    vector <pair <int, int>> ans;
    pair <int, int> A, B, lst_B = { 999, -1e5 }, tkn = { -1, 0 };
    //tkn-last taken
    int i = -1;
    pair <int, int> lst_ans;
    while (i < sz) {
        if (i == -1) {
            if (!x.empty()) {
                if (x[0].first > 0) break;
            }
            while (i < sz) {
                ++i;
                if (i == sz) break;
                B = x[i];
                //cout << "B = ";
                //cp(B);
                if (B.first <= 0) {
                    //cout << "ONE\n";
                    if (B.second > lst_B.second) {
                        //cout << "TWO\n";
                        lst_B = B;
                        if (i == sz - 1) ans.pshb(lst_B);
                    }
                }
                else {
                    //cout << "lst_B = ";
                    //cp(lst_B);
                    ans.pshb(lst_B);
                    tkn = lst_B;
                    break;
                }
            }
        }
        else {
            auto A = x[i];
            if (A.first > tkn.second) break;
            //cout << "A = ";
            //cp(A);
            /*if ((int)ans.size() > 0) {
                cout << "last in ans = ";
                cp(ans[(int)ans.size() - 1]);
            }*/
            if ((int)ans.size() >= 1) {
                lst_ans = ans[(int)ans.size() - 1];
                if (lst_ans.second >= m) break;
            }
            ans.pshb(A);
            lst_ans = ans[(int)ans.size() - 1];
            if (lst_ans.second >= m) break;
            /*if ((int)ans.size() > 0) {
                cout << "last in ans = ";
                cp(ans[(int)ans.size() - 1]);
            }*/
            while (i < sz) {
                ++i;
                if (i == sz) break;
                B = x[i];
                //cout << "B = ";
                //cp(B);
                if (B.first <= A.second) {
                    //cout << "ONE\n";
                    if (B.second > lst_B.second) {
                        //cout << "TWO\n";
                        lst_B = B;
                        if (i == sz - 1) ans.pshb(lst_B);
                    }
                }
                else {
                    //cout << "lst_B = ";
                    //cp(lst_B);
                    ans.pshb(lst_B);
                    tkn = lst_B;
                    break;
                }
            }
        }

    }
    if ((int)ans.size() >= 1) {
        lst_ans = ans[(int)ans.size() - 1];
    }
    //cout << "taken sections num = " << (int)ans.size() << '\n';
    //ct(ans);
    if ((int)ans.size() == 0 || lst_ans.second < m) {
        cout << "No solution\n";
    }
    else {
        cout << (int)ans.size() << '\n';
        for (auto y : ans) {
            cout << y.first << ' ' << y.second << '\n';
        }
    }
}
//WA
/*
100
-1 1
1 99
99 101
0 100
0 0
*/
/*
100
0 20
10 50
50 70
0 0
*/
/*
100
-10 10
5 30
20 50
30 70
30 80
50 70
50 110
90 120
0 0
*/
//smth bad with idx
/*
100
0 20
10 50
50 70
80 90
90 110
0 0
*/
//check what takes
/*
/*
100
0 20
10 50
50 70
80 90
90 110
70 85
0 0
*/