Zadanie Vasya and sets Eolymp, problem z bitsetem / maskami bitowymi

Question

Mam problem z takim zadaniem: https://www.eolymp.com/en/contests/14738/problems/149026

Zapewne jest ono jakies proste, napisałem kod na 80pkt(przekroczono limit czasu) przy pomocy bitseta. Zastanawiam się dlaczego nie wchodzi na 100pkt, pewnie coś źle napisałem w bitsecie, czy te and-owanie / or-owanie / count nie powinny działać w O(SIZE / 64)? Jest to moje pierwsze zadanie, w którym skorzystałem z bitseta, więc z góry ostrzegam może być tragicznie....

Kod:

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

int n = 0, m = 0, z = 0, wczytana_liczba = 0, a = 0, b = 0, wyn = 0;
const unsigned long long SIZE = 1e6+1;
string decyzja;
vector<bitset<SIZE>> czy_mamy;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    czy_mamy.assign(n,{});

    for (int i = 0; i < n; ++i)
    {
        cin >> z;
        while(z--)
        {
            cin >> wczytana_liczba;
            czy_mamy[i].set(wczytana_liczba);
        }
    }

    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> decyzja >> a >> b;
        a--, b--;
        if (decyzja == "INTERSECTION")
            cout << (czy_mamy[a] & czy_mamy[b]).count() << '\n';
        else
            cout << (czy_mamy[a] | czy_mamy[b]).count() << '\n';
    }

    return 0;
}

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Raczej jest dobrze. Limity czasowe są pewnie kiepsko ustawione. Samo wczytanie 20 * 1e6 liczb z wejścia jest całkiem czasochłonne, więc trzeba bawić się w jakieś mikrooptymalizacje.

Spróbuj zamienić cin na getline i potem sparsuj stringa. Wywołanie getline 20 razy powinno być trochę szybsze niż wywołanie cin 20*1e6 razy.

Comments

Sprawdziłem na swoim sprzęcie i przy optymalizacji O2, na których chyba przeważnie działają sprawdzarki, getline działa jakieś 9 razy szybciej. Bez O2 działają podobnie, choć getline wciąż minimalnie szybciej

---

@Whistleroosh, 

chyba limity są źle ustawione. Średnio popisała się ta platforma.

Ale i tak dzięki, napewno to przyśpieszyło,