• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Kolejka SPOJ

VPS Starter Arubacloud
0 głosów
1,180 wizyt
pytanie zadane 31 maja 2016 w C i C++ przez Hohlik741 Nowicjusz (160 p.)

Rozwiązuje zadanie na SPOJ, tutaj link: http://pl.spoj.com/problems/AL_01_02/

Nie mam już pomysłów jak przyśpieszyć program, cały czas wypluwa o przekroczonym czasie sad... Bardzo proszę was o pomoc, może ktoś mnie naprowadzi na sprytniejsze rozwiązanie.

Tutaj mój kod, który wydaje mi się teraz najszybszy:

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n;
    cin>>n;
    for(int g=0; g<n; g++)
    {
        string pom;
        char kolej[1000000];
        int dl;
        cin>>kolej;
        dl=strlen(kolej);
        pom=kolej[dl-1];
        for(int i=dl-2; i>=0; i--)
        {
            if(kolej[dl-1]>kolej[i])
            {
                continue;
            }
            else
            {
                char znak;
                znak=kolej[dl-1];
                pom=znak+pom;
            }
            dl=i+1;
            if(dl==1)
            {
                char znak;
                znak=kolej[dl-1];
                pom=znak+pom;
            }
        }
        cout<<pom<<endl;
        }
        return 0;

}

 

2 odpowiedzi

0 głosów
odpowiedź 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
Jest to zadanie na najdłuższy podciąg rosnący. Radzę poczytać:
http://informatyka.wroc.pl/node/402?page=0,3
komentarz 23 czerwca 2016 przez CharlieGG Użytkownik (900 p.)
Nie to nie jest zadanie na najdłuższy podciąg rosnący ;)
komentarz 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
Jak to nie? Treść zadania można by podać tak:
dostaniesz t ciągów znaków. Wypisz najdłuższy podciąg niemalejący z każdego z nich
komentarz 23 czerwca 2016 przez CharlieGG Użytkownik (900 p.)
W takim razie czemu dla pierwszego testu przykładowego odpowiedź to "n", a nie np. "kkn", albo "kkkn"? (w zależności czy szukamy spójnego czy nie).
komentarz 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
edycja 23 czerwca 2016 przez p0m0
Zgadzam się. Popełniłem błąd. Przepraszam.
komentarz 23 czerwca 2016 przez Hohlik741 Nowicjusz (160 p.)
No niestety, gdyby to był najdłuższy podciąg rosnący to raczej problemów by nie było... Ktoś ma jakieś inne pomysły ?
komentarz 24 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
Do rozwiązania zadania potrzeba złożoności liniowej do każdego przykładu, ale to daje TLE. Wydaje mi się, że trzeba użyć innej biblioteki niż iostream, albo innego języka niż c++
komentarz 24 czerwca 2016 przez CharlieGG Użytkownik (900 p.)
Zajrzyj w najlepsze wysyłki. Prawie wszyscy zrobili to w C++, więc nie mów że nie można używając C++ :) Sam zrobiłem to w tym języku, więc się da. Co prawda iostream niekoniecznie wystarczy, ale jeśli zamienimy cout na putchar to spokojnie wejdzie.
0 głosów
odpowiedź 23 czerwca 2016 przez CharlieGG Użytkownik (900 p.)
przywrócone 23 czerwca 2016 przez CharlieGG

Po pierwsze, gdy używasz iostream na SPOJu to zawsze dodawaj tą linijkę od razu po mainie:

ios_base::sync_with_stdio(0);

Bez tej linijki rozwiązania używające iostreama bardzo często dostają TLE na SPOJu. 

Po drugie, Twój program nie działa poprawnie na teście przykładowym.

EDIT: Sorry za odkop, nie spojrzałem na datę.

komentarz 24 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
Mimo, że program nie działa poprawnie, to inne, działające poprawnie też mają TLE.

Warto też używać cin.tie(NULL);
komentarz 6 sierpnia 2016 przez Hohlik741 Nowicjusz (160 p.)
Omyłkowo wrzuciłem niepoprawny kod... Zastosowałem obie porady i niestety dalej czas przekroczony :/

Podobne pytania

0 głosów
0 odpowiedzi 1,107 wizyt
pytanie zadane 4 lipca 2016 w C i C++ przez xjakubekx Obywatel (1,280 p.)
0 głosów
1 odpowiedź 219 wizyt
0 głosów
1 odpowiedź 675 wizyt
pytanie zadane 12 lutego 2019 w C i C++ przez matiks1991 Nowicjusz (120 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...