SPOJ, zadanie Kolejka - przekroczono limit czasu

Witam ponownie,
Zadanie: http://pl.spoj.com/problems/AL_01_02/
Wyrzuca błąd: przekroczono limit czasu
Dla danych testowych na SPOJU działa, testowane dla przykładów:

3
sdaadd
asldfdaklfjskdvnxcnsdfsdgfksvnkjv
zzyvgf

Wynik:
sddd
xvv
zzyvgf

Również działa prawidłowo - problemem jest czas wykonania programu.
Ma ktoś pomysł jak to przyspieszyć ? Z góry dziękuje.

#include <iostream>
#include <list>

using namespace std;

void kolejnosc(string c);

int main()
{
    int t;
    string ciag;
    cin >> t;
    while(t--)
    {
        cin >> ciag;
        kolejnosc(ciag);
    }
    return 0;
}

void kolejnosc(string c)
{
    list <char> zwierzeta;
    list <char>::iterator it = zwierzeta.begin();

    for(int i=0;i<c.length();i++)
    {

        if(zwierzeta.empty() || (int)zwierzeta.back()>=(int)c[i])
            zwierzeta.push_back(c[i]);

        else if((int)zwierzeta.back() == (int)(c[i]) - 1)
        {
            while(it != zwierzeta.begin() && (int)zwierzeta.back() == (int)(c[i]) - 1)
                --it;
            zwierzeta.insert(it, c[i]);
        }

        else if((int)zwierzeta.back() < (int)(c[i]) - 1)
        {
            while(it != zwierzeta.begin() && (int)zwierzeta.back() < (int)(c[i]) - 1)
                zwierzeta.pop_back();
            zwierzeta.insert(it, c[i]);
        }

        it = zwierzeta.end();

    }

    while(!zwierzeta.empty())
    {
        cout << zwierzeta.front();
        zwierzeta.pop_front();
    }
    cout << endl;

}
 

jeżeli pracujesz tylko na front i end to proponuję zmianę kontenera z std::list na std::deque na początek

edit:
nie wiem czy przekroczenie czasu jest równoznaczne z poprawnym wykonaniem zadania, chyba nie

gośćabc napisał(a):

jeżeli pracujesz tylko na front i end to proponuję zmianę kontenera z std::list na std::deque na początek

Odpada - zobacz na kod, używam wstawiania w środek struktury ( insert ). Rozważałem kolejkę ale niestety ona tego nie posiada.

Wiara czyni cuda napisał(a):

gośćabc napisał(a):

jeżeli pracujesz tylko na front i end to proponuję zmianę kontenera z std::list na std::deque na początek

Odpada - zobacz na kod, używam wstawiania w środek struktury ( insert ). Rozważałem kolejkę ale niestety ona tego nie posiada.

no to reserve i vector

męczyłęm się chyba z 4 godziny i nie dałem rady tego czasu nie przekroczyć,
z 15 różnych podejść

oto moje ostatnie:

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <deque>
#include <cstdint>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <memory>
#include <set>
#include <tuple>

std::string actualQueue(std::string& order);

int main()
{
	int t;
	std::string ciag;
	std::cin >> t;
	std::vector<std::string> inputs;
	while(t--)
	{
		std::cin >> ciag;
		inputs.push_back(ciag);
	}
	for(auto& input : inputs) {
		std::cout << actualQueue(input);
	}

	return 0;
}

std::string actualQueue(std::string& animalOrder)
{
	std::string const zoo = "zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA";
	std::string resultQueue;
	resultQueue.reserve(animalOrder.size());
	char animal;

	for(auto animalIt = std::begin(zoo) ; animalIt != std::end(zoo) ; ++animalIt) {
		animal = *animalIt;

		size_t occurenceCount = std::count(std::begin(animalOrder), std::end(animalOrder), animal);
		if(occurenceCount > 0) {
			std::fill_n(std::back_inserter(resultQueue), occurenceCount, animal);
			animalOrder.erase(0, animalOrder.find_last_of(animal) + 1);
		}

		if(!animalOrder.size()) {
			break;
		}
	}

	return resultQueue;
}

może Ci to jakoś pomoże

Nie no robienie tego w O(n²) to na pewno nie jest dobre rozwiązanie ;) Szczególnie że już bardzo naiwna optymalizacja daje O(nlogn) bo z racji że w ciągu zwierząt występuje pewien porządek (słabsze zwierzęta za sileniejszymi) to spokojnie punkt do którego stos jest usuwany można wyszukac sobie w czasie O(logn) szukając połówkowo.
Co wiecej na dobrą sprawę to można by to pewnie nawet zrobić zupełnie liniowo jakby sobie pamiętać gdzie w ciągu występuje dana literka na samym przodzie, bo wtedy nawet szukać nie trzeba.
No i ja bym jednak używał tablicy a nie dynamicznie alokowanego stosu i po prostu trzymał sobie gdzieś informacje który indeks określa wierzchołek stosu. Wtedy pop prawie całego stosu to po prostu jedno przypisanie na zasadzie stack_top = x a nie potencjalnie milion operacji na dynamicznie alokowanej liscie.

Na SPOJ chyba sobie żarty robią tym zadaniem, bo nie wiem co innego myśleć, gdy algorytm o złożoności liniowej nie mieści się w wyznaczonym czasie.

#include <iostream>
#include <string>

int main()
{
	int z;
	std::cin >> z;

	while (z--)
	{
		std::string animals;
		std::cin >> animals;

		char max = *animals.rbegin();
		unsigned last = animals.size() - 1;

		for (int i = animals.size() - 2; i >= 0; --i)
			if (animals[i] >= max)
				animals[--last] = max = animals[i];

		for (; last < animals.size(); ++last)
			std::cout << animals[last];

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

	return 0;
}

Przecież to jest proste zadanie które daje złożoność o(n).
Nie potrzebna jest żadna kolejka, lista czy inne cuda. Wystarczy sam string, którego należy kopiować o tyłu z odpowiednim warunkiem. Zwierzaka kopiujemy tylko wtedy, jeśli poprzedni zwierz nie był silniejszy od poprzedniego kopiowanego zwierza. Ot cała filozofia.

Pebal napisał(a):

Na SPOJ chyba sobie żarty robią tym zadaniem, bo nie wiem co innego myśleć, gdy algorytm o złożoności liniowej nie mieści się w wyznaczonym czasie.

To jest jedno z tych durnych zadań, w których sprawność wczytywania danych jest ważna. Zauważ, że dane wejściowe są bardzo duże.
Ergo trzeba wyłączyć synchronizację z stdio zaraz po starcie programu.

@Pebal: faktycznie coś jest nie tak, nawet takie coś nie przechodzi: http://ideone.com/7mWWot (zoptymalizowane IO).