Ryhmät

input/code.cpp: In function 'int main()':
input/code.cpp:89:37: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if (toiveet_voimassa.size() < koko) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <map>
 
using namespace std;

typedef pair<int, int> P;

struct Vaihe {
    int edellinen_vaihe;
    int ryhmän_koko;
    bool onnistuu = false;
    unordered_set<int> käytetyt;
    unordered_map<int, int> jatkot;
};

int main() {
    iostream::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    vector<pair<int, int>> toiveet(n);
    for (int i = 0; i < n; i++) {
        cin >> toiveet[i].first >> toiveet[i].second;
    }
    sort(toiveet.begin(), toiveet.end());

    vector<vector<int>> testit(t);
    int ryhmien_määrä_yhteensä = 0;
    for (auto &testi : testit) {
        int ryhmien_määrä;
        cin >> ryhmien_määrä;
        testi.resize(ryhmien_määrä);
        for (int i = 0; i < ryhmien_määrä; i++) {
            cin >> testi[i];
        }
        sort(testi.begin(), testi.end());
        ryhmien_määrä_yhteensä += ryhmien_määrä;
    }

    // Tehdään graafi
    vector<int> vastausvaiheet;
    vector<Vaihe> vaiheet;
    vaiheet.reserve(ryhmien_määrä_yhteensä + 1);
    vaiheet.push_back(Vaihe{-1, 0, true});
    for (auto& testi : testit) {
        int vaihe = 0;
        for (int koko : testi) {
            if (!vaiheet[vaihe].jatkot.count(koko)) {
                vaiheet[vaihe].jatkot[koko] = (int)vaiheet.size();
                vaiheet.push_back(Vaihe{vaihe, koko});
            }
            vaihe = vaiheet[vaihe].jatkot[koko];
        }
        vastausvaiheet.push_back(vaihe);
    }

    set<P> seuraavat;
    for (auto& jatko : vaiheet[0].jatkot) {
        seuraavat.insert({jatko.first, jatko.second});
    }

    set<P> toiveet_voimassa;
    int toive_i = 0;

    const int d = 0;
    while (!seuraavat.empty()) {
        int koko, vaihe_i;
        tie(koko, vaihe_i) = *seuraavat.begin();
        seuraavat.erase(seuraavat.begin());

        if(d) cout << "Koko " << koko << ", vaihe " << vaihe_i << "\n";
        while (!toiveet_voimassa.empty() && toiveet_voimassa.begin()->first < koko) {
            if (d) cout << " - " << toiveet[toiveet_voimassa.begin()->second].first << " " << toiveet[toiveet_voimassa.begin()->second].second << "\n";
            toiveet_voimassa.erase(toiveet_voimassa.begin());
        }
        while (toive_i < n && toiveet[toive_i].first <= koko) {
            if (toiveet[toive_i].second >= koko) {
                if (d) cout << " + " << toiveet[toive_i].first << " " << toiveet[toive_i].second << "\n";
                toiveet_voimassa.insert({toiveet[toive_i].second, toive_i});
            }
            toive_i++;
        }
        if (toiveet_voimassa.size() < koko) {
            if(d) cout << "  -> ei onnistu, jatketaan\n";
            continue; // Tämä vaihe ei onnistu, jatkoja ei ole syytä tutkia.
        }

        auto& vaihe = vaiheet[vaihe_i];
        int puuttuu = koko;
        for (auto toive: toiveet_voimassa) {
            int toive_i = toive.second;
            if (vaihe.käytetyt.count(toive_i)) continue;
            vaihe.käytetyt.insert(toive_i);
            puuttuu--;
            if (puuttuu == 0) break;
        }
        if (puuttuu == 0) {
            vaihe.onnistuu = true;
            for (auto& jatko : vaihe.jatkot) {
                if(d) cout << " == " << jatko.first << " " << jatko.second << "\n";
                seuraavat.insert({jatko.first, jatko.second});
                vaiheet[jatko.second].käytetyt = vaihe.käytetyt;
            }
            vaihe.käytetyt.clear();
            vaihe.jatkot.clear();
        } else {
            if(d) cout << "  -> ei onnistu, jatketaan\n";
        }
    }

    for (auto i: vastausvaiheet) {
        cout << (vaiheet[i].onnistuu ? "YES\n" : "NO\n");
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED