Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Jak przyśpieszyć działanie programu?

Ostatnio zmodyfikowano 2020-07-31 17:20
Autor Wiadomość
Godzik
Temat założony przez niniejszego użytkownika
Jak przyśpieszyć działanie programu?
» 2020-07-30 22:14:43
C/C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio( 0 );
    vector < int > A[ 100001 ];
    int n, k;
    cin >> n >> k;
   
    for( int i = 0; i < k; i++ )
    {
        int u, v;
        cin >> u >> v;
        A[ u ].push_back( v );
    }
    for( int i = 1; i <= n; i++ )
    {
        cout << "Zbiornik " << i << ": ";
        for( int j = A[ i ].size() - 1; j >= 0; j-- )
        {
            cout << A[ i ][ j ] << " ";
        }
        cout << "\n";
    }
    return 0;
}
Oto treść zadania:
W Górach Opatowskich znajdują się zbiorniki tajemniczego składnika X.
Codziennie o godzinie 5:00 jest dowożona beczka z napisaną na niej liczbą naturalną
i umieszczana w jednym z N zbiorników. Jaś w trakcie obozu informatycznego
przypadkiem natknął się w lesie na teczkę z informacją, że łącznie składowane będzie
M beczek oraz z informacją która beczka trafi do którego zbiornika.
Jaś w trakcie spaceru spostrzegł, że zbiorniki są głębokie i na tyle wąskie,
że po wrzuceniu do niego beczki ląduje ona na poprzednio wrzuconej beczce lub na dnie,
jeżeli do zbiornika nie wrzucono wcześniej żadnej beczki.
Jaś jest ciekaw, jaki ciąg liczb powstanie jeśli zaczniemy wyciągać beczki
z któregoś zbiornika i odczytywać liczby napisane na kolejnych beczkach.

Zadanie
Napisz program, który znając zawartość teczki znalezionej przez Jasia,
poda dla każdego zbiornika ciąg liczb, jaki powstanie przy wyciąganiu z niego beczek.

Wejście
N - liczba zbiorników (1 <= N <= 10^5)
M - liczba beczek (1 <= M <= 10^6)
W następnych M liniach po dwie liczby Xi, Yi,
odpowiednio liczba napisana na i-tej beczce (1 <= Xi <= 10^9)
i numer zbiornika, do którego trafi i-ta beczka (1 <= Yi <= N)

Wyjście
N lini, w i-tej linii napis "Zbiornik #i: " oraz ciąg oddzielonych spacjami liczb,
jakie byłyby odczytywane przy wyciąganiu kolejnych beczek z i-tego zbiornika.

Przykład
Dla danych wejściowych

3 7
12 2
5 1
100 1
37 3
1 2
2 1
23 2
poprawną odpowiedzią jest
Wyjście:
Zbiornik 1: 2 100 5
Zbiornik 2: 23 1 12
Zbiornik 3: 37
P-177398
pekfos
» 2020-07-31 17:20:13
Trzeba tu opracować specjalizowaną strukturę danych. Zadanie nie miałoby sensu, gdyby wystarczyła tablica wektorów. Nie napisałeś za bardzo czego oczekujesz, więc na razie zostawię tylko ogólny kierunek, żebyś mógł jeszcze sam pomyśleć nad zadaniem. Daj znać jak na coś wpadniesz, albo będzie potrzebne bardziej precyzyjne nakierowanie.
Kluczowe jest zminimalizowanie ilości alokacji pamięci i kopiowania danych, ale nie możesz po prostu zrobić tablicy N x M, bo to setki gigabajtów, a pewnie masz do dyspozycji mniej niż jeden. Da się tu osiągnąć zużycie pamięci proporcjonalne do N + M, zarezerwowane z góry jedną alokacją.
P-177399
« 1 »
  Strona 1 z 1