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

Zadanie Promocja finał OI, optymalizacja pamięci - set

Object Storage Arubacloud
0 głosów
248 wizyt
pytanie zadane 24 stycznia 2023 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z optymalizacją tego zadania z finału 7 OI-a: https://szkopul.edu.pl/problemset/problem/VD_bKhKPiYjm8uq-R8O1r88h/site/?key=statement

Kod jest bardzo prosty. Oprócz wczytania danych jest dokładnie 5 linii.

#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0;
ll wyn = 0;
multiset<int> S;

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

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            S.insert(wczytana_liczba);
        }
        wyn += *S.rbegin() - *S.begin();
        S.erase(S.lower_bound(*S.begin()));
        S.erase(S.lower_bound(*S.rbegin()));
    }
    printf("%lld",wyn);
    return 0;
}

Przechodzi tylko na 80pkt, wywala się pamięć. Pewnie trzeba dobrać jakąś lepszą strukturę danych, ma ktoś jakiś pomysł?

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

komentarz 24 stycznia 2023 przez j23 Mędrzec (194,920 p.)

wywala się pamięć.

Co to znaczy? Jakiś błąd wykonania, czy po prostu program przekracza limit?

komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
dostępna pamięc na zadanie to 32MB, a program przekracza limit.
komentarz 24 stycznia 2023 przez j23 Mędrzec (194,920 p.)
Próbowałeś użyć wektora?
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak wsumie, sobie myślę, że na rozwiązanie tego w dobrej pamięci są 2 opcje:

1 - To co ja zrobiłem z drzewami przedziałowymi punkt-przedział min i max. O(n log n)

2 - Zaimplementować kopiec binarny i też by przeszło w O(n log n).

Set z tego co wyczytałem to jest bardzo pamieciożerny. To zadanie jest z finału OI-a a jest bardzo proste.

I kopiec by działał jak max_val > 10^6, a to działa tylko dlatego, bo max val <= 10^6

1 odpowiedź

0 głosów
odpowiedź 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Przeszło już na 100pkt w O(n log n), korzystając z tego, że max val <= 10^6 zrobiłem drzewo przedziałowe minów i drzewo przedziałowe maxów i pamięć jest liniowa, bo drzewo przedziałowe to vector. Kod

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0, base = 0, rozmiar_drzewa = 0, min_zap = 0, max_zap = 0;
ll wyn = 0;
vector<int> ile(1e6+1,0);
vector<int> drzewo_przedzialowe_max;
vector<int> drzewo_przedzialowe_min;

void update_min(int v, int val)
{
    v += base;
    drzewo_przedzialowe_min[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_min[v] = min(drzewo_przedzialowe_min[v * 2], drzewo_przedzialowe_min[v * 2 + 1]);
        v /= 2;
    }
}

void update_max(int v, int val)
{
    v += base;
    drzewo_przedzialowe_max[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_max[v] = max(drzewo_przedzialowe_max[v * 2], drzewo_przedzialowe_max[v * 2 + 1]);
        v /= 2;
    }
}

int querry_min(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = 1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res,drzewo_przedzialowe_min[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_min[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

int querry_max(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = -1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = max(res,drzewo_przedzialowe_max[l+1]);
        if (p % 2 == 1)
            res = max(res, drzewo_przedzialowe_max[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

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

    base = (1 << ((int)ceil((double)log2(1e6+1))));
    rozmiar_drzewa = base * 2;
    drzewo_przedzialowe_min.assign(rozmiar_drzewa,1e6+5);
    drzewo_przedzialowe_max.assign(rozmiar_drzewa,0);

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            ile[wczytana_liczba]++;
            update_min(wczytana_liczba,wczytana_liczba);
            update_max(wczytana_liczba,wczytana_liczba);
        }
        max_zap = querry_max(1,1e6);
        //cout << "MAX ZAP: " << max_zap << endl;
        ile[max_zap]--;
        if (ile[max_zap] == 0)
        {
            update_max(max_zap,0);
            update_min(max_zap,1e6+5);
        }
        min_zap = querry_min(1,1e6);
        ile[min_zap]--;
        if (ile[min_zap] == 0)
        {
            update_max(min_zap,0);
            update_min(min_zap,1e6+5);
        }
        wyn += max_zap - min_zap;
        //cout << "Wyn:" << wyn << endl;
    }
    printf("%lld",wyn);
    return 0;
}

 

komentarz 24 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
Można też zwykłą mapą zrobić
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A mapa ma mniejszą pamięc niż set?
komentarz 24 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
Powinna mieć mniej więcej taką samą pamięć. Ale przynajmniej redukuje duplikaty i może to pomogło
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mapa też wchodzi na 100(pamięc spoko), z czasami praktycznie takimisamymi jak drzewo przedziałowe. W niektórych testach minimalnie gorzej, w niektórych minimalnie lepiej. Wniosek taki, że gdy nie trzeba robić żadnego find-a albo coś takiego, to lepiej użyć mapy.

Zauważyłem, że na OI-u mają taki bardzo dziwny zwyczaj, że jak nie zależy na pamięci to dają np 1GB, 512MB, 256MB, 128MB albo coś takiego, a jak zależy to dają np 64MB, 32MB itp. xD
komentarz 25 stycznia 2023 przez j23 Mędrzec (194,920 p.)

@Whistleroosh, 

Ale przynajmniej redukuje duplikaty i może to pomogło

A std::set nie?

komentarz 25 stycznia 2023 przez Whistleroosh Maniak (56,980 p.)
Racja, mówiłem to w odniesieniu do multiseta użytego w zadaniu.
komentarz 27 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@pasjonat_algorytmiki, 

btw, bardzo podobne zadanie na drzewo punkt-przedział po wartościach: 

https://sio2.mimuw.edu.pl/c/zwo21/p/naj-cpp/

Bardzo polecam.

Podobne pytania

0 głosów
1 odpowiedź 257 wizyt
0 głosów
1 odpowiedź 119 wizyt
0 głosów
1 odpowiedź 188 wizyt
pytanie zadane 19 maja 2023 w C i C++ przez Dani Obywatel (1,450 p.)

92,558 zapytań

141,407 odpowiedzi

319,569 komentarzy

61,945 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...