• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie meteory finał XVIII OI, równoległe wyszukiwanie binarne

VPS Starter Arubacloud
0 głosów
218 wizyt
pytanie zadane 17 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
zmienione kategorie 17 kwietnia 2023 przez pasjonat_algorytmiki

Mam problem z zadaniem meteory z finału XVIII OI: https://szkopul.edu.pl/problemset/problem/czzVm7v3I58TnPHzBgWiyELT/site/?key=statement

Zobaczyłem je w przygodach, trochę nad nim pomyślałem, przeczytałem rozwiązanie i wydawało mi się, że je rozumiem, robimy zwykłe wyszukiwanie binarne, ale żeby nie robić dła każdego oddzielnie, to robimy je równolegle, czyli trzymamy rekurencyjnie i dzielimy je na części. Wszystko było fajnie, nawet się ucieszyłem, że poznałem nowy algorytm, napisałem go, uśmiechnięty, że będzie setka, a tu się okazało, że jest zero i w wszystkich testach oprócz 3 przykładowych przekroczono limit czasu. Kompletnie nie wiem o co chodzi. Kod wydaje się być prosty. Czyli najprawdopodobniej nie rozumiem tej idei...

Strona 184 w książeczce OI, to rozwiązanie, co wydaje mi się, że je rozumiem. Znaczy wydawało mi się, bo teraz to wiem, że czegoś nie rozumiem, tylko jeszcze nie wiem czego.

Mój kod:

#include <iostream>
#include <vector>

using namespace std;

struct Opad
{
    int l;
    int r;
    int ile_dod;
};

int n = 0, m = 0, k = 0, base = (1 << 19), rozmiar_drzewa = base * 2;
vector<int> drzewo_przedzialowe;
vector<int> idxy_poczatkowe;
vector<int> zapotrzebowanie;
vector<int> stacje;
vector<int> wyn;
vector<Opad> opady;

inline void update (int l, int p, int val)
{
    l = l + base - 1, p = p + base + 1;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            drzewo_przedzialowe[l+1] += val;
        if (p % 2 == 1)
            drzewo_przedzialowe[p-1] += val;
        l /= 2;
        p /= 2;
    }
}

inline void dodaj (int l, int p, int val)
{
    if (l <= p)
        update(l,p,val);
    else
    {
        update(l,m-1,val);
        update(0,p,val);
    }
}

inline int query(int v)
{
    v += base;
    int res = 0;
    while (v > 0)
    {
        res += drzewo_przedzialowe[v];
        v /= 2;
    }
    return res;
}

inline void clearuj_drzewo_przedzialowe()
{
    drzewo_przedzialowe.assign(rozmiar_drzewa,0);
}

inline void binary_searchh(int l, int p, vector<int> idxy)
{
    if (p - l == 1)
    {
        for (int i = 0; i < idxy.size(); ++i)
            wyn[idxy[i]] = p;
    }
    else
    {
        int srodek = (l + p) / 2;
        clearuj_drzewo_przedzialowe();
        for (int i = 0; i < srodek; ++i)
            dodaj(opady[i].l-1, opady[i].r-1, opady[i].ile_dod);
        vector<int> ile;
        ile.assign(n+1,0);
        for (int i = 0; i < m; ++i)
            ile[stacje[i]] += query(i);
        vector<int> vect_lewych, vect_prawych;
        for (int i = 0; i < idxy.size(); ++i)
        {
            if (ile[idxy[i]] >= zapotrzebowanie[idxy[i]])
                vect_prawych.push_back(idxy[i]);
            else
                vect_lewych.push_back(idxy[i]);
        }
        binary_searchh(l,srodek,vect_prawych);
        binary_searchh(srodek,p,vect_lewych);
    }
}

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

    cin >> n >> m;

    zapotrzebowanie.assign(n+1,-1);
    wyn.assign(n+1,-1);
    stacje.assign(m,-1);

    for (int i = 0; i < m; ++i)
        cin >> stacje[i];

    for (int i = 1; i <= n; ++i)
        cin >> zapotrzebowanie[i];

    cin >> k;
    opady.assign(k,{});
    for (int i = 0; i < k; ++i)
        cin >> opady[i].l >> opady[i].r >> opady[i].ile_dod;

    clearuj_drzewo_przedzialowe();
    idxy_poczatkowe.assign(n,0);
    for (int i = 0; i < n; ++i)
        idxy_poczatkowe[i] = i+1;
    binary_searchh(-1,k+1,idxy_poczatkowe);

    for (int i = 1; i <= n; ++i)
    {
        if (wyn[i] == k+1)
            cout << "NIE" << '\n';
        else
            cout << wyn[i] << '\n';
    }

    return 0;
}

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

komentarz 17 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Już chyba rozumiem, że to jest za wolne, i trzeba to normalnie iterscyjnie trzymać, chyba wiem jak to zrobić.

1 odpowiedź

+1 głos
odpowiedź 17 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Przeszło na 100pkt. Mój problem był taki, że nie rozumiałem idei równoległego wyszukiwania binarnego. To co tam naklepałem ma TLE, bo jest conajmiej O(N^2 * lg N), jak nie więcej. Ono jest trikiem jak mając dane N zdarzeń i dla każdego puścić wyszukiwanie binarne, przyśpieszyć to pusczając to raz. Cała idea jest taka, że jak dla kolejnych zdarzeń trzeba sprawdzić stan po np. 5, 3, 10 deszczach, to zamiast symulować z drzewem przedziałowym dla każdego z N miast kolejne deszcze, to robimy to tak jakby gąsienicą. Naliczamy stan po 3 deszczach, sprawdzamy dla tego, co interesuje nas po 3 deszczach i potem jak mamy po 5 deszczach, to nie naliczamy od nowa, tylko do tego stanu po 3 deszczach dokładamy po 4,5, sprawdzamy dla tego po 5, potem dla tego po dziesięciu nie liczymy od nowa, tylko do tego co mamy(po pięciu) dokładamy po 6,7,8,9,10. I tak dla wszystkich elementów. Dlatego to jest szybkie, bo nie naliczamy dla każdego od nowa. Chyba najłatwiej te zdarzenia posortować od najmiejszych(ja tak zrobiłem) Świetna technika! Bardzo mi się podoba.

Kod:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Opad
{
    int l;
    int r;
    int ile_dod;
};

struct Element
{
    int l;
    int p;
    int srodek;
    int idx_miasta;
    bool operator < (const Element &element) const
    {
        return srodek < element.srodek;
    }
};

int n = 0, m = 0, k = 0, base = (1 << 19), rozmiar_drzewa = base * 2;
vector<ll> drzewo_przedzialowe;
vector<int> zapotrzebowanie;
vector<int> stacje;
vector<int> wyn;
vector<Opad> opady;
vector<vector<int>> jakie_idxy_ma_miasto;
vector<Element> elementy;

inline void update (int l, int p, ll val)
{
    l = l + base - 1, p = p + base + 1;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            drzewo_przedzialowe[l+1] += val;
        if (p % 2 == 1)
            drzewo_przedzialowe[p-1] += val;
        l /= 2;
        p /= 2;
    }
}

inline void dodaj (int l, int p, ll val)
{
    if (l <= p)
        update(l,p,val);
    else
    {
        update(l,m-1,val);
        update(0,p,val);
    }
}

inline ll query(int v)
{
    v += base;
    ll res = 0;
    while (v > 0)
    {
        if (drzewo_przedzialowe[v] > 1e9) // Zeby nie przekroczylo sie z long longa.
            return 1e9+5;
        res += drzewo_przedzialowe[v];
        v /= 2;
    }
    return res;
}

inline void clearuj_drzewo_przedzialowe()
{
    drzewo_przedzialowe.assign(rozmiar_drzewa,0);
}

int main()
{
    // Rownolegle wyszukiwanie binarne po wyniku, https://forum.pasja-informatyki.pl/583882/zadanie-meteory-final-xviii-oi-rownolegle-wyszukiwanie-binarne?show=583891#a583891
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    zapotrzebowanie.assign(n+1,-1);
    wyn.assign(n+1,-1);
    stacje.assign(m,-1);
    jakie_idxy_ma_miasto.assign(n+1,{});

    for (int i = 0; i < m; ++i)
        cin >> stacje[i];

    for (int i = 0; i < m; ++i)
        jakie_idxy_ma_miasto[stacje[i]].push_back(i);

    for (int i = 1; i <= n; ++i)
        cin >> zapotrzebowanie[i];

    cin >> k;
    opady.assign(k,{});
    for (int i = 0; i < k; ++i)
        cin >> opady[i].l >> opady[i].r >> opady[i].ile_dod;

    for (int i = 1; i <= n; ++i)
        elementy.push_back({0,k+1,(k+1) / 2, i});
    sort(elementy.begin(), elementy.end());

    while(!elementy.empty())
    {
        int wsk = 0;
        vector<Element> nowy;
        clearuj_drzewo_przedzialowe();
        for (int i = 0; i < k and wsk < elementy.size(); ++i)
        {
            dodaj(opady[i].l-1, opady[i].r-1, opady[i].ile_dod);
            while(true)
            {
                if (elementy[wsk].srodek - 1 == i)
                {
                    ll sum = 0;
                    for (int j = 0; j < jakie_idxy_ma_miasto[elementy[wsk].idx_miasta].size(); ++j)
                        sum += query(jakie_idxy_ma_miasto[elementy[wsk].idx_miasta][j]);
                    int poczatek = 0, koniec = 0;
                    if (sum >= zapotrzebowanie[elementy[wsk].idx_miasta] or sum > 1e9)
                    {
                        poczatek = elementy[wsk].l, koniec = elementy[wsk].srodek;
                    }
                    else
                    {
                        poczatek = elementy[wsk].srodek, koniec = elementy[wsk].p;
                    }
                    if (koniec - poczatek == 1)
                        wyn[elementy[wsk].idx_miasta] = koniec;
                    else
                        nowy.push_back({poczatek, koniec, (poczatek + koniec) / 2, elementy[wsk].idx_miasta});
                    wsk++;
                }
                else
                    break;
            }
        }
        elementy = nowy;
        sort(elementy.begin(), elementy.end());
    }

    for (int i = 1; i <= n; ++i)
    {
        if (wyn[i] == k+1)
            cout << "NIE" << '\n';
        else
            cout << wyn[i] << '\n';
    }

    return 0;
}

Podobne pytania

0 głosów
1 odpowiedź 138 wizyt
0 głosów
1 odpowiedź 706 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 621 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,845 zapytań

141,784 odpowiedzi

320,859 komentarzy

62,178 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...