• 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
205 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ź 133 wizyt
0 głosów
1 odpowiedź 659 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 574 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,768 zapytań

141,695 odpowiedzi

320,510 komentarzy

62,106 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.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...