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

Obliczanie najdłuższego, rosnącego podciągu

Ostatnio zmodyfikowano 2011-12-27 23:19
Autor Wiadomość
matoł115
Temat założony przez niniejszego użytkownika
Obliczanie najdłuższego, rosnącego podciągu
» 2011-12-27 23:19:12
Witam! Tym razem mam napisać program liczący Najdłuższy podciąg rosnący
Oto dokładna treść zadania:

Zamek

Limit czasowy: 8s, Limit pamięciowy: 32MB.
Grasz w grę Zamek. W każdej turze możesz awansować swój zamek na pewien poziom i za każdy awans (nieważne o ile poziomów, ważne, że o co najmniej 1) dostajesz 1 punkt zwycięstwa. Udało ci się jednak podejrzeć pliki konfiguracyjne gry i wiesz, jakie będą kolejne poziomy, na które, w kolejnych turach, będzie można awansować zamek. Ponadto wiesz, że w $ k $-tej turze wykorzystanie możliwości awansu kosztuje $ 2^{k} $ dukatów. Policz więc, ile punktów zwycięstwa uda ci się zdobyć. Jeśli masz więcej możliwości, wybierz tę o najmniejszym koszcie. (Zauważ, że im wcześniej się zdecydujesz na awans, tym lepiej!). Zaczynasz od poziomu 0.
Wejście
W pierwszej linii wejścia znajdziesz ilość gier, które chcesz rozegrać. W każdej następnej znajduje się ilość tur $ n $ $ (n \leq 5*10^{5}) $, a następnie $ n $ liczb $ a_{i} $ $ (1\ \leq a_{i}\ \leq 10^{9}) $ określające na jaki poziom możesz awansować zamek w $ i $-tej turze.
Wyjście
Dla każdej gry wypisz jedną linię: niech zaczyna się od liczby $ m $ oznaczającej ilość punktów zwycięstwa, które możesz uzyskać, a następnie $ m $ liczb oznaczających kolejne poziomy (bez zerowego), które będziesz uzyskiwać, grając optymalnie.
Przykład
Dla danych wejściowych:
3
6 1 5 2 7 7 10
3 3 2 1
4 1 2 3 4

Poprawną odpowiedzią jest:
4 1 5 7 10
1 3
4 1 2 3 4
Wyjaśnienie:
W pierwszym teście awansujemy kolejno: 0 -> 1 -> 5 -> 7 -> 10. Koszt takiego przedsięwzięcia to 2+4+16+64 = 86.
W drugim możemy tylko raz awansować, więc robimy to najniższym kosztem = 2.
W trzecim uda nam się zdobyć pełen komplet punktów.

Oto mój program:
C/C++
#include <vector>
#include <cstdio>
using namespace std;
int main()
{
    int z, j, k;
    scanf( "%d", & z );
    for( j = 0; j < z; j++ )
    {
        int a, i, p, x, y, z, n = 0;
        scanf( "%d", & a );
        vector < int > v[ a ];
        for( i = 0; i < a; i++ )
        {
            scanf( "%d", & p );
            x = 0;
            y = i;
            while( x <= y )
            {
                if( i == 0 )
                {
                    v[ 0 ].push_back( p );
                    n++;
                    break;
                } else
                {
                    z =( x + y ) / 2;
                    if( v[ z ].size() == 0 )
                    {
                        if( v[ z - 1 ].size() > 0 )
                        {
                            if( v[ z - 1 ].back() < p )
                            {
                                v[ z ].push_back( p );
                                n++;
                                break;
                            } else
                            {
                                y = z - 1;
                            }
                        } else
                        {
                            y = z - 1;
                        }
                    } else
                    {
                        if( v[ z ].back() < p )
                        {
                            x = z + 1;
                        }
                        if( v[ z ].back() == p )
                        {
                            break;
                        }
                        if( v[ z ].back() > p )
                        {
                            if( z == 0 )
                            {
                                v[ 0 ].push_back( p );
                                break;
                            }
                            if( z != 0 )
                            {
                                if( v[ z - 1 ].back() < p )
                                {
                                    v[ z ].push_back( p );
                                } else
                                {
                                    y = y - 1;
                                }
                            }
                        }
                       
                       
                    }
                }
            }
        }
        vector < int > wynik;
        p = v[ n - 1 ][ 0 ];
        wynik.push_back( v[ n - 1 ][ 0 ] );
        for( i = n - 1; i >= 0; i-- )
        {
            x = 0;
            y = v[ i ].size() - 1;
            while( x <= y )
            {
                z =( x + y ) / 2;
                if( v[ i ][ z ] < p )
                {
                    if( z == 0 )
                    {
                        p = v[ i ][ z ];
                        wynik.push_back( p );
                        break;
                    } else
                    {
                        if( v[ i ][ z - 1 ] > p )
                        {
                            p = v[ i ][ z ];
                            wynik.push_back( p );
                            break;
                        } else
                        {
                            y = z - 1;
                        }
                    }
                }
                if( v[ i ][ z ] >= p )
                {
                    x = z + 1;
                }
            }
        }
        printf( "%d ", wynik.size() );
        for( i = wynik.size() - 1; i >= 0; i-- )
        {
            printf( "%d ", wynik[ i ] );
        }
        printf( "\n" );
    }
    return 0;
}
I wyniki:

Test Wynik Czas Pamięć
zam1.out accepted 0 ms 1004
zam2.out wrong answer 0 ms 1004
zam3.out accepted 0 ms 1004
zam4.out accepted 1899 ms 15500
zam5.out accepted 436 ms 31296
Czy ma ktoś pomysł co tutaj może być źle?
Pozdrawiam
P-46424
« 1 »
  Strona 1 z 1