Submission #871922

#	Time	Username	Problem	Language	Result	Execution time	Memory
871922		tvladm2009	Event Hopping 2 (JOI21_event2)	C++17	8 / 100	41 ms	3036 KiB

event2

#include <bits/stdc++.h>
 
using i64 = long long;
 
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        std::cin >> l[i] >> r[i];
    }
    if (n <= 20) {
        std::vector<std::vector<int>> good; 
        for (int mask = 1; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != k) {
                continue;
            }
            std::vector<std::pair<int, int>> v;
            for (int b = 0; b < n; b++) {
                if (mask & (1 << b)) {
                    v.push_back({l[b], r[b]});
                }
            }
            sort(v.begin(), v.end());
            bool ok = true;
            for (int i = 1; i < v.size(); i++) {
                if (v[i].first < v[i - 1].second) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                std::vector<int> rep;
                for (int b = 0; b < n; b++) {
                    if (mask & (1 << b)) {
                        rep.emplace_back(b);
                    }
                }
                good.emplace_back(rep);
            }
        }
        if (good.empty()) {
            std::cout << "-1\n";
            return 0;
        }
        std::sort(good.begin(), good.end());
        std::vector<int> sol = good[0];
        for (auto i : sol) {
            std::cout << i + 1 << "\n";
        }
        return 0;
    }

    std::vector<int> dp(n, 0), suff(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        int lft = i + 1, rgh = n - 1, pos = n;
        while (lft <= rgh) {
            int m = (lft + rgh) / 2;
            if (l[m] >= r[i]) {
                rgh = m - 1;
                pos = m;
            } else {
                lft = m + 1;
            }
        }
        dp[i] = suff[pos] + 1;
        suff[i] = std::max(suff[i + 1], dp[i]);
    }
    std::vector<int> sol;
    int last = 0;
    for (int i = 0; i < n; i++) {
        if (l[i] >= last && dp[i] >= k) {
            last = r[i];
            k--;
            sol.push_back(i + 1);
        }
        if (k == 0) {
            break;
        }
    }
    if (k > 0) {
        std::cout << "-1\n";
        return 0;
    }
    for (auto it : sol) {
        std::cout << it << "\n";
    }
    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:29:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |             for (int i = 1; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61