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;
}