» Forum » Programowanie » [C, C++] Szukam pomocy

Ciąg zer

Ostatnio zmodyfikowano 2020-05-03 00:45

Autor Wiadomość

Kinzoku99

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:

#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

pekfos

» 2020-05-02 12:59:24

Pełna treść zadania. Nie wiadomo po co jest dana k.

P-176776

Kinzoku99

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

pekfos

» 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:

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

Kinzoku99

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

pekfos

» 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

Kinzoku99

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

» Forum » Programowanie » [C, C++] Szukam pomocy