Zadanie Bracia

Question

Witam.

Rozwiązuję to zadanie << https://szkopul.edu.pl/problemset/problem/KkZDP16mELVF692Bf-NJsN1L/site/?key=statement. Nie mam pojęcia dlaczego nie przechodzi mi mój kod większości przypadków w testach. Ogólnie to wyznaczam końce i początki dla vectora bracia -> preprocessinguję tablicę początków i końców -> wyznaczam początek i koniec dla preprocessingu -> robię dp

Będę wdzięczny jak ktoś może rzucić oko na kod.
Z góry dziękuję.

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

using namespace std;

const int maxn = 1e6 + 5;
int poczatek[maxn];
int koniec[maxn];
std::vector<int> bracia;
std::vector<int> preprocessing;
int dp[maxn*2];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    
    bracia.push_back(0);

    for(int i=1;i<=n;++i){
        int x;
        std::cin >> x;

        bracia.push_back(x);
    }

    //poczatek dla bracia
    for(int i=1;i<=n;++i)
        poczatek[i] = -1;
    
    for(int i=1;i<=n;++i)
        if(poczatek[bracia[i]] == -1)
            poczatek[bracia[i]] = i;
    
    //koniec dla bracia
    for(int i=1;i<=n;++i)
        koniec[i] = -1;
    
    for(int i=n;i>=1;--i)
        if(koniec[bracia[i]] == -1)
            koniec[bracia[i]] = i;
    
    //preprocessing 3 2 4 2 5 - > 3 3 2 4 4 2 5 5
    preprocessing.push_back(0);
    for(int i=1;i<=n;++i){
        if(poczatek[bracia[i]] == koniec[bracia[i]])
        {
            preprocessing.push_back(bracia[i]);
            preprocessing.push_back(bracia[i]);
        }
        else if(poczatek[bracia[i]] == i || koniec[bracia[i]] == i)
            preprocessing.push_back(bracia[i]);
    }

    //poczatek dla preprocessing
    for(int i=1;i<=preprocessing.size()-1;++i)
        poczatek[i] = -1;
    
    for(int i=1;i<=preprocessing.size()-1;++i)
        if(poczatek[preprocessing[i]] == -1)
            poczatek[preprocessing[i]] = i;
    
    //koniec dla preprocessing
    for(int i=1;i<=preprocessing.size()-1;++i)
        koniec[i] = -1;
    
    for(int i=preprocessing.size()-1;i>=1;--i)
        if(koniec[preprocessing[i]] == -1)
            koniec[preprocessing[i]] = i;
    
    //dp
    dp[0] = 0;
    for(int i=1;i<=preprocessing.size()-1;++i){
        if(i == koniec[preprocessing[i]])
            dp[i] = max(dp[poczatek[preprocessing[i]]] + 1,dp[i-1]);
        else
            dp[i] = dp[i-1];
    }

    cout << dp[preprocessing.size()-1] << '\n';
    return 0;
}

 

Answer 1

for(int i=1;i<=preprocessing.size()-1;++i)
    poczatek[i] = -1;

czyścisz pozycje od 1 do preprocessing.size(), a potem w kodzie robisz poczatek[preprocessing[i]] = i; Tylko, że w treści zadania nie ma założenia, że preprocessing[i] <= preprocessing.size().

Comments

Bardzo dziękuję Ci za pomoc. Teraz wchodzi już prawie na 100 pkt. W ostatnim teście wypisuje memory limit exceeded. Z tego co rozumiem to za dużo używam tablic/vectorów.

---

Możesz próbować skorzystać z reserve, żeby zarezerwować dokładnie tyla pamięci ile trzeba. Tak samo tablicę dp możesz tworzyć dopiero wtedy gdy wiadomo ile będzie miała elementów

---

Zainteresował mnie ten reserve. Widzę, że sporo kodu trzeba wpisać żeby z tego korzystać, chyba, że źle zrozumiałem kod w przykładzie.

W Rust jest podobny mechanizm, można podać przewidywaną liczbę elementów a później rozszerzać wielkość kontenera. Ale tam to jest jedna linijka kodu.

---

Tu też wystarczy jedna linia np. v.reserve(50)

---

To dobrze, mnie zmyliła:

struct NAlloc

Czy Szkopuł w ogólnym rankingu bierze pod uwagę liczbę wersji nadesłanego kodu? Niektóre strony biorą to pod uwagę.

---

Raczej nie

---

@Whistleroosh, Działa! Dzięki wielkie (;

---

@Whistleroosh, Czy reserve dodaje też na swoje miejsca zera tak jak resize?

---

Reserve nie zmienia rozmiaru wektora. Jak masz wektora v rozmiaru 10, to po v.reserve(100) on wciąż ma rozmiar 10. Tablica z której wewnętrznie korzysta v zwiększyła się, ale i tak nie masz bezpośredniego dostępu do nowych pól, więc nie ważne czy tam jest zero czy cokolwiek.