Kopiowanie vectorów

Question

Cześc,

Robiąc zadanie z programowania dynamicznego, musze kopiować na kolejkę vectory. Dostaję 64 pkt za zad, kopiowanie vectora 30 elementowego trochę zajmuje (powtarzam to bardzo dużo razy).

Mój kod:

generowanie.push(generowanie.front().czy_zawiera); // To jest tablica booli.

Mam pomysł, żeby dodać do zadania listę sąsiedztwa i to może pomóc, jednak chciałem się najpierw dowiedzieć czy da się to kopiowanie zrobić szybciej?

I jeszce drugie pytanie. Takie kopiowanie ma złożonność O(n)?

Comments

Możesz pokazać więcej kodu? W szczególności, typy?

---

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

using namespace std;

struct Element_kolejki
{
    long long suma = 0;
    int liczba_elementow = 0;
    vector<bool> czy_zawiera;
};

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

    long long n = 0;
    long long k = 0;
    long long m = 0;
    long long wczytany_klocek = 0;
    long long max_suma = 0;
    vector<long long> klocki;
    queue<Element_kolejki> generowanie;
    unordered_set<long long> sumy;

    cin >> n >> k >> m;

    vector<bool> poczatek(n,false);

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytany_klocek;
        if (wczytany_klocek <= m)
        {
            klocki.push_back(wczytany_klocek);
        }
    }

    for (int i = 0; i < klocki.size(); ++i)
    {
        if (auto it = sumy.find(klocki[i]) == sumy.end())
        {
            max_suma = max(klocki[i],max_suma);
            generowanie.push({klocki[i],1,poczatek});
            generowanie.back().czy_zawiera[i] = true;
        }
    }

    while(!generowanie.empty())
    {
        for (int i = 0; i < klocki.size(); ++i)
        {
            if (generowanie.front().czy_zawiera[i] == false && generowanie.front().suma + klocki[i] <= m)
            {
                if (generowanie.front().liczba_elementow < k)
                {
                    if (generowanie.front().suma + klocki[i] == m) // Musimy tutaj sprawdzac bo jak wyzej to niewiadomo czy nie przekracza limitu k.
                    {
                        cout << m;
                        return 0;
                    }
                    else
                    {
                        if (auto it = sumy.find(generowanie.front().suma+klocki[i]) == sumy.end())
                        {
                            generowanie.push({generowanie.front().suma+klocki[i],generowanie.front().liczba_elementow+1,generowanie.front().czy_zawiera});
                            sumy.insert(generowanie.front().suma+klocki[i]);
                            max_suma = max(max_suma,generowanie.front().suma+klocki[i]);
                            generowanie.back().czy_zawiera[i] = true;
                        }
                    }
                }
            }
        }
        generowanie.pop();
    }

    cout << max_suma;
    return 0;
}

 

---

Zmieniłem typy z int na short i long long na int, bo wystarczało i przyśpieszyło na 73 pkt.