Ciąg zer
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Ciąg zer

AutorWiadomość
Temat założony przez niniejszego użytkownika
Ciąg zer
» 2020-05-02 12:24:24
Mam problem z kolejnym zadaniem, również działa ciut za wolno.
Dane:
n - długość vectora a, 5 <= n <= 500 000
k - liczba zmian w ciągu (0 na 1 i 1 na 0), 1 <= k <= 200 000
a - vector znaków '0', '1'

Wyjście:
Po każdej zmianie wypisuje długość najdłuższego ciąg kolejnych zer

Algorytm działa na zasadzie drzewa przedziałowego structów v, który przechowuje ile w danym przedziale jest '0' z lewej i prawej strony i oraz m - maksymalną ilość zer w przedziale (w korzeniu drzewa pojawia się odpowiedź)
Bardzo bym podziękował za jakąś podpowiedź co tu można usprawnić ;)

Kod:
C/C++
#include <stdio.h>
#include <vector>
using namespace std;

struct v
{
    int lewo;
    int prawo;
    int m;
};

int maxx( int a, int b )
{
    if( a > b )
         return a;
    else
         return b;
   
}

int pmaxl( vector < v > d, int i, int n )
{
    if( d[ 2 * i ].lewo == int( n /( i + 1 ) ) )
         return 1;
    else
         return 0;
   
}

int pmaxp( vector < v > d, int i, int n )
{
    if( d[ 2 * i + 1 ].prawo == int( n /( i + 1 ) ) )
         return 1;
    else
         return 0;
   
}

void ustaw( vector < v > & d, int i, int n )
{
    if( d[ 2 * i + 1 ].prawo == d[ 2 * i ].prawo && pmaxl( d, i, n ) ) {
        //cout << "Opcja 1. d(" << i << ")\n";
        d[ i ].m = d[ 2 * i ].m * 2;
        d[ i ].prawo = d[ 2 * i ].prawo * 2;
        d[ i ].lewo = d[ 2 * i ].lewo * 2; }
    else if( pmaxl( d, i, n ) ) {
        //cout << "Opcja 2. d(" << i << ")\n";
        d[ i ].lewo = d[ 2 * i ].m + d[ 2 * i + 1 ].lewo;
        d[ i ].prawo = d[ 2 * i + 1 ].prawo;
        d[ i ].m = d[ 2 * i ].m + d[ 2 * i + 1 ].lewo;
        /*d[i].m = maxx(d[i].m,d[2*i+1].m);*/ }
    else if( pmaxp( d, i, n ) ) {
        //cout << "Opcja 3. d(" << i << ")\n";
        d[ i ].prawo = d[ 2 * i ].prawo + d[ 2 * i + 1 ].m;
        d[ i ].lewo = d[ 2 * i ].lewo;
        d[ i ].m = d[ 2 * i ].prawo + d[ 2 * i + 1 ].m;
        /*d[i].m = maxx(d[i].m,d[2*i].m);*/ }
    else {
        //cout << "Opcja 4. d(" << i << ")\n";
        d[ i ].lewo = d[ 2 * i ].lewo;
        d[ i ].prawo = d[ 2 * i + 1 ].prawo;
        d[ i ].m = d[ 2 * i ].prawo + d[ 2 * i + 1 ].lewo;
        d[ i ].m = maxx( d[ i ].m, d[ 2 * i ].m );
        d[ i ].m = maxx( d[ i ].m, d[ 2 * i + 1 ].m ); }
}

void UPDATE( vector < v > & d, int k, int n )
{
    k +=( n - 1 );
    if( d[ k ].m == 0 ) {
        d[ k ].m = 1;
        d[ k ].lewo = 1;
        d[ k ].prawo = 1; }
    else if( d[ k ].m == 1 ) {
        d[ k ].m = 0;
        d[ k ].lewo = 0;
        d[ k ].prawo = 0; }
    int p = k / 2;
    while( p > 0 )
    {
        ustaw( d, p, n );
        p /= 2;
    }
   
    printf( "%d\n", d[ 1 ].m );
}


int main()
{
    int n, m;
    scanf( "%d", & n );
    scanf( "%d", & m );
    vector < int > z( m, 0 );
    vector < char > a( n, 0 );
    getchar();
    for( int i = 0; i < n; i++ )
         a[ i ] = getchar();
   
    for( int i = 0; i < m; i++ )
         scanf( "%d", & z[ i ] );
    //n = a.size();
    int M = n;
    int sh = 0;
    while( n >>= 1 ) ++sh;
   
    n = 1 << sh;
    if( n != M ) n *= 2;
   
    for( int i = M; i < n; i++ )
         a.push_back( '1' );
   
    v t;
    t.lewo = - 1;
    t.prawo = - 1;
    t.m = - 1;
    vector < v > d( 2 * n, t );
   
    //tworzenie drzewa
    for( int i = 0; i < n; i++ )
    if( a[ i ] == '0' ) {
        d[ n + i ].lewo = 1;
        d[ n + i ].prawo = 1;
        d[ n + i ].m = 1;
    }
    else if( a[ i ] == '1' ) {
        d[ n + i ].lewo = 0;
        d[ n + i ].prawo = 0;
        d[ n + i ].m = 0;
    }
    for( int i = n - 1; i > 0; i-- )
         ustaw( d, i, n );
   
    //wykonywanie programu
    for( int i = 0; i < m; i++ )
         UPDATE( d, z[ i ], n );
   
    return 0;
}
P-176775
» 2020-05-02 12:59:24
Pełna treść zadania. Nie wiadomo po co jest dana k.
P-176776
Temat założony przez niniejszego użytkownika
» 2020-05-02 17:40:06
pekfos, dana k jak napisałem jest liczbą zmian ciągu. Służy do tego, żeby pętle po nim dać tych zmian. Na wyjściu również jest k wierszy, czyli długość najdłuższego ciągu 0 po zmianie. Działa to tak: Mamy na przykład ciąg 001000, w którym  pozycje są numerowane od 1 do 6. Program oczywiście wypełnia go do najbliższej potęgi 2 czyli 00100011 (1 są nie ważne bo liczymy zera) I np. całe wejście jest takie:
6 2
001000
3
3
To ma wyrzucić wynik 6 bo po zmianie na 3 pozycji program widzi 00000011 czyli 6 zer obok siebie a potem po kolejnej 3 wróci do 00100011 czyli wyrzuci 3 bo nadłuższy ciąg zer obok siebie ma długość 3
P-176785
» 2020-05-02 22:40:35
6 2
001000
3
3
To nie jest zgodne ze specyfikacją wejścia, jaką opisałeś. Następnym razem kopiuj treść.

No ale dobra, zacznijmy od najgłupszych błędów:
C/C++
int pmaxl( vector < v > d, int i, int n )
{
    if( d[ 2 * i ].lewo == int( n /( i + 1 ) ) )
         return 1;
    else
         return 0;
   
}

int pmaxp( vector < v > d, int i, int n )
{
    if( d[ 2 * i + 1 ].prawo == int( n /( i + 1 ) ) )
         return 1;
    else
         return 0;
   
}
Wywołanie tych funkcji spowoduje skopiowanie wektora przekazanego przez argument. Powinno być const vector < v >& d.
P-176797
Temat założony przez niniejszego użytkownika
» 2020-05-02 22:48:49
Kurcze faktycznie przyspieszyło program 3krotnie tylko pojawiły się błędy ;) Czas debugować, dziękuję
P-176798
» 2020-05-02 22:51:48
Polecam zaznajomić się z profilerem i w takich sytuacjach po prostu uruchamiać pod nim program, podając na wejście w miarę pesymistyczny przypadek danych. Dane bierz z pliku, albo na potrzeby testu generuj losowo w samym programie.
P-176800
Temat założony przez niniejszego użytkownika
» 2020-05-03 00:45:17
Tak czy tak zadanie naprawione już wchodzi ;)
P-176803
« 1 »
 Strona 1 z 1