Jak zmniejszyć pamięć zajmowaną przez program?

Question

W sprawdzarce pokazuj, że został przekroczony limit pamięci :/  zmieniłam typy na (wydaje mi się) najmniejsze z możliwych i tak nie pomogło :/ może czymś trzeba zastąpić wektor? tylko czym :/ poniżej wklejam mój kod oraz treść zadania.

#include <iostream>
#include <vector>
using namespace std;
float a;
vector <float> V;
short int i;
short int x, y;
int main()
{
    V.push_back(-1);
cin>>x;
while(x>0)
{
    cin>>y;
    //cin>>a;
   // V.push_back(a);
    // cout<<1<<" ";
    while(y>0)
    {

        cin>>a;
        i=0;
        while (V[i]>=a)
        {
         i++;
        }
        V.insert(V.begin()+i,a);
        cout<<i+1<<" ";
        y--;
    }
    V.clear();
x--;
}
//for(int i=0;i<V.size();i++)
//{
   // cout<<V[i]<<endl;
//}


return 0; }

Ranking

Masz napisać moduł do systemu obsługi konkursów programistycznych. Twój moduł będzie dostawał zapytania zawierające liczbę punktów uczestników konkursu. Dla każdego uczestnika musisz określić na której pozycji w rankingu znajdzie się w danym momencie, biorąc pod uwagę wyniki dotychczas wprowadzone do modułu - podobnie jak w trakcie zawodów w skokach narciarskich. Pozycję określa liczba zdobytych punktów (im więcej tym wyższa pozycja). Jeżeli kilku uczestników posiada taką samą liczbę punktów, o pozycji decyduje kolejność zgłoszeń (im późniejsze zgłoszenie tym niższa pozycja). Liczbę punktów podaje się w postaci liczby rzeczywistej dziesiętnej z dokładnością do pierwszego miejsca po przecinku.

Zadanie

 

Napisz program, który dla każdego kolejnego zgłoszenia uczestnika będzie podawał jego aktualną pozycję w rankingu.

 

Wejście

 

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna, określająca liczbę zestawów danych, które za chwilę pojawią się na wejściu.
W pierwszym wierszu zestawu znajduje się jedna liczba naturalna niemniejsza niż 1 i niewiększa niż 10000. Określa ona liczbę zgłoszeń uczestników konkursu. W kolejnym wierszu znajduje się ciąg nieujemnych liczb rzeczywistych (z co najwyżej jedną cyfrą po przecinku) niewiększych niż 50, oddzielonych pojedynczymi spacjami. Liczby w tym wierszu określają liczbę punktów z jakimi zgłaszali się kolejni uczestnicy.

 

Wyjście

 

Dla każdego zestawu danych musisz wypisać w jednym wierszu ciąg liczb oddzielonych pojedynczymi spacjami. Liczby mają odpowiadać miejscom jakie w momencie zgłoszeń będą zajmować uczestnicy konkursu.

 

Przykład

 

Dla wejścia:

4
5  0.0  0.1  0.2  0.3  0.4
6  49.7  44.3  32.1  28.9  17.4  3.5
4  25.0  25.0  25.0  25.0
4  31.7  0.0  25.2  50.0

 

poprawnym rozwiązaniem jest:

1  1  1  1  1
1  2  3  4  5  6
1  2  3  4
1  2  2  1

Comments

Czy ten kod jest do tego zadania? Bo nie wygląda jakby był do niego napisany

---

faktycznie, przepraszam. już poprawiłam

---

Na początku dodałaś do vectora wartość -1 i to był całkiem dobry pomysł, ale zauważ, że pod koniec iteracji pierwszej pętli zerujesz ten vektor, czyli w kolejne iteracji tego -1 tam nie będzie, co może powodować różne błędy

---

Faktycznie to błąd ale problem jest jeszcze z czasem :(

---

Można to zrobić na drzewach przedziałowych, wtedy działałoby w O(nlogn)

---

taki jest aktualny pomysł, zobaczę czy to pomoże

---

Skoro V zawiera zbiór posortowany, można użyć std::lower_bound:

int main()
{
    float a;
    std::vector<float> V;
    int i, x, y;

    std::cin >> x;

    while (x-- > 0) {
        std::cin >> y;

        V.clear();
        V.reserve(y);
        
        while (y-- > 0) {
            std::cin >> a;

            auto it = std::lower_bound(V.rbegin(), V.rend(), a);
            i = std::distance(it, V.rend()) ;
            V.insert(V.begin() + i, a);
            
            std::cout << i + 1 << " ";
        }

        std::cout << '\n';
    }

    return 0;
}

Powinno być ciut szybciej od wyszukiwania liniowego.

---

mam błąd w kompilatorze w wierszu " auto it = std::lower_bound(V.rbegin(), V.rend(), a);"

"error: 'it' does not name a type|"

---

Pewnie nie kompilujesz w c++11. Ale nawet jeżeli uda Ci się skompilować, to ten program i tak będzie pewnie wychodził poza limit czasowy. On korzysta z niewielkiej optymalizacji względem Twojego pomysłu. Dopiero to drzewo przedziałowe bardzo przyspieszy program

---

@gryzedywany,

std::vector<float>::reverse_iterator it = std::lower_bound(V.rbegin(), V.rend(), a);

 

---

@j23 wychodzi poza limit czasowy