CF2_kafuma's blog

By CF2_kafuma, history, 8 years ago, In English

that's my code , and i can't understand why i have RUNTime_Error?? can someone explain me??

Limite = input();
Valores = map(int, raw_input().split());
Permutacion = map(lambda x: int(x) - 1, raw_input().split());

Rpta = [0];
Visitado = [False]*Limite;
DSU = range(Limite);
DSUValor = [0]*Limite;


def Find(posicion):
    if posicion != DSU[posicion]:
        DSU[posicion] = Find(DSU[posicion]);
    return DSU[posicion];


def Union(A, B):
    Pos_A = Find(A);
    Pos_B = Find(B);
    DSU[Pos_B] = Pos_A;
    DSUValor[Pos_A] += DSUValor[Pos_B];


for x in reversed(Permutacion):
    Visitado[x] = True;
    DSUValor[ x ] = Valores[ x ];
    if x - 1 >= 0 and Visitado[x - 1]:
        Union(x, x - 1);
        #Valores[ x ] += Valores[ Find( x -1 ) ];
        #DSU[ Find( x - 1 ) ] = x;
    if x + 1 < Limite and Visitado[x + 1]:
        Union(x, x + 1);
        #Valores[x] += Valores[Find(x + 1)];
        #DSU[Find(x + 1)] = x;
    #DSUValor[x] += Valores[x];
    Rpta.append(max( Rpta[-1], DSUValor[x]));

print '\n'.join(map(str, reversed(Rpta[:-1 ])));

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By CF2_kafuma, history, 8 years ago, In English

i was create a algorithm to solved 671B and i did that:

that running with O( n*log(n) ) { well, i think so } but th judgement gave "RunTime_ERROR", why do you think??? and how can i better my algorithm??

#include <iostream>
#include<algorithm>
#include<stdio.h>

using namespace std;
/*
    1) idead: using two priority queue to recover the Max and Min values and subtraccion each other.
        time => O( n*log(n)*k )--> can swap values max and min on Minimo and Maximo,

    2) idead : using a map tree to sort all values and operate on tree
        time => O( n*log( n ) + K*log( n ) ) --> find max/min in O( log(n) )

    3) using range of values are diference between min again this value, and operate using range to reduce
       K on the time.
       time => O( n*log^2( n ) )

*/
unsigned int Rango = 1;
unsigned int x = 0;
unsigned int K = 0;
unsigned int N = 0;
unsigned int Mover = 0;
unsigned int Mayor, Menor;
unsigned int LimiteMx, LimiteMn;


unsigned int Civiles[ 500000 ];

unsigned int BuscarSgte(){
    int fin = N -1 ; int inicio = 0;
    int medio = (N - 1)/2;

    while( fin != inicio + 1 ){
            if( Civiles[ medio ] > Civiles[ 0 ] ) fin = medio;
            else if( Civiles[ medio ] == Civiles[ 0 ] && Civiles[ medio + 1] == Civiles[ 0 ] ) inicio = medio;
            else break;
            medio = ( fin + inicio )/2;
    }

    return ( Civiles[ medio + 1 ] == Civiles[0] )? medio + 1 : medio ;
}

unsigned int BuscarAnterior(){
    int medio = (N-1)/2;
    int fin = N - 1; int inicio = 0;

    while( fin != 1 + inicio ){
        if( Civiles[ medio ] < Civiles[ N - 1 ])
            inicio = medio;
        else if( Civiles[ medio ] == Civiles[ N - 1 ] && Civiles[ medio - 1 ] == Civiles[ N - 1 ] )
            fin = medio;
        else
            break;

        medio = ( fin + inicio ) / 2;
    }

    return ( Civiles[ medio ] == Civiles[ N - 1] )? medio: medio + 1;

}

void Actualizar(  int Mn, int Mx , int Base ){
    for( int i = 0; i < Base ; i++ ){
        Civiles[ Mn - i ] += 1;
        Civiles[ Mx + i ] -= 1;
    }
}

int main()
{

    scanf("%i %i", &N , &K );

    for( int i = 0; i < N; i++ ){
        scanf("%i", &Civiles[i] );
    }

    sort(Civiles, Civiles+N);

    while( K > 0 ){
        if( Civiles[ 0 ] + 1 == Civiles[ N - 1 ] || Civiles[0] == Civiles[ N - 1 ] ) break;

        LimiteMx = BuscarAnterior();
        LimiteMn = BuscarSgte();

        Mayor = ( N - LimiteMx )*( Civiles[  N - 1 ] - Civiles[ LimiteMx - 1 ] );
        Menor = ( LimiteMn + 1 )*( Civiles[ LimiteMn + 1 ] - Civiles[ 0 ] );

        Mover = min( Menor, Mayor );
        if( K <= Mover ){
            Actualizar( LimiteMn , LimiteMx , K );
            K = 0;
        }else{
            Actualizar( LimiteMn, LimiteMx , Mover );
            K = K - Mover;
        }

    }

    cout <<  Civiles[ N - 1 ] - Civiles[ 0 ] ;


    return 0;
}


Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it