Mniejsze niż

[Szemek]

Zadanie pochodzi z systemu SPOJ

Dany jest zbiór \(\displaystyle{ A}\) złożony z \(\displaystyle{ n}\) liczb naturalnych. Mając liczbę naturalną \(\displaystyle{ i}\) wyznacz, ile jest w zbiorze A liczb od niej mniejszych.

Wejście

W pierwszym wierszu podana jest liczba \(\displaystyle{ n<10^6}\) , czyli moc zbioru \(\displaystyle{ A}\). Następnie kolejne \(\displaystyle{ n}\) wierszy zawiera elementy \(\displaystyle{ A}\). Są to liczby naturalne z zakresu \(\displaystyle{ [1..10^{30}-1]}\)
Następnie podana jest liczba \(\displaystyle{ k<10^6}\) oraz w kolejnych \(\displaystyle{ k}\) wierszach podawane są liczby naturalne \(\displaystyle{ i_1,..., i_k}\) z zakresu \(\displaystyle{ [1..10^{30}-1]}\).

Wyjście

Dla każdej liczby \(\displaystyle{ i_s}\) należy podać ile elementów w zbiorze A jest mniejszych od \(\displaystyle{ i_s}\).

Moje rozwiązanie nie zalicza czasowo ostatniego testu.
Kod programu w C++.

Ukryta treść:    

Ze względów wydajnościowych korzystam ze strumieni z C.

Kod: Zaznacz cały

#include<cstdio>
#include<vector>
#include<list>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
	int n;
	char text[31];
	scanf("%d",&n);
	vector< vector<string> > tab(30);
	while(n--)
	{
		scanf("%s",text);
		string str_text(text);
		tab[str_text.length()-1].push_back(text);
	}
	for(int i=0; i<30; i++)
		sort(tab[i].begin(),tab[i].end());
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",text);
		string str_text(text);
		int ans = 0;
		int len = str_text.length()-1;
		for(int i = 0; i < len; i++)
			ans += tab[i].size();
		vector<string>::iterator pos = lower_bound(tab[len].begin(), tab[len].end(), str_text);
		ans += distance(tab[len].begin(), pos);
		printf("%d\n", ans);
	}
}

Opis działania:
Liczby wczytuję jako ciągi znaków.
Stworzyłem sobie 'dynamiczną tablicę' (vector) 30 'dynamicznych tablic' stringów (ciągów znaków). Każda wewnętrzna tablica przechowuje stringi o danej długości od 1 do 30. Po wczytaniu i wrzuceniu w odpowiednie miejsce następuje sortowanie w wewnętrznych tablicach.
Przy zliczaniu dodaję sumuję rozmiary (ilość elementów) tablic przechowujących stringi o mniejszej długości, a później zliczam elementy z tablicy o danej długości.

Tak wygląda moje podejście do tego problemu. Jak mogę to zrobić optymalniej Jakie zastosować struktury Wszelkie porady mile widziane.

[spajder]

1. Nie bardzo rozumiem, przechowujesz liczby jako stringi? To strasznie spowalnia i zżera dużo pamięci.
2. Zaalokouj pamięć na wektor po wczytaniu n (vector.reverve()), unikniesz wielokrotnego realokowania i przenoszenia danych - dla miliona elementów może to być kilkadziesiąt czy kilkaset razy.
3. Ogólnie wczytaj liczby do tablicy, posortuj ją a następnie leciutko zmodyfikuj algorytm wyszukiwania binarnego.

[Szemek]

1. Nie bardzo rozumiem, przechowujesz liczby jako stringi? To strasznie spowalnia i zżera dużo pamięci.

Żaden typ całkowity nie przechowa mi tak dużych liczb \(\displaystyle{ 10^{30}-1}\)
Stringi są dosyć ciężkie, lżejszym rozwiązaniem będzie tablica znaków.
Może do tego jakiś Radix Sort, hmm...

Zaalokouj pamięć na wektor po wczytaniu n

Racja, alokacja pamięci w tym przypadku wydaje mi się o wiele lepszym rozwiązaniem.

[adamadam]

Żaden typ całkowity nie przechowa mi tak dużych liczb \(\displaystyle{ 10^{30}-1}\)
Stringi są dosyć ciężkie, lżejszym rozwiązaniem będzie tablica znaków.

Zauważ, że np. do takiego longlonga zmieścisz 15 cyfrową liczbę. Wystarczy użyć systemu np. o podstawie \(\displaystyle{ 10^{15}}\) i przechowywać jedną taką liczbę jako dwa longlongi (dość znany trik ). Łatwo można napisać potrzebne operatory, żeby móc to posortować stlowym sortem i używać binary searcha. Nie robiłem tego zadania ale myślę, że to powinno pomóc.

Zapewne ten test na którym twój program ma TLE to same 30 cyfrowe liczby różniące się między sobą na ostatnich miejscach To sprawia, że porównywanie tych stringów działa długo, a twoja optymalizacja z tablicami na liczby o różnych długościach nic nie daje.