TOPIC

Time limit exceeded

Andre Marasca asked 2 years ago

Olá, estou usando métodos rápidos para ler e escrever, usando ordenação O(n log n) mas ta dando Time limit exceeded

#include <stdio.h>
#include <stdlib.h>

int compareints (const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

int values[3000000];

int main (void)
{
    int c, NC, N, i;
    scanf("%d", &NC);
    for(c = 0; c < NC; c++)
    {
        scanf("%d", &N);
        for(i = 0; i < N; i++)
            scanf("%d", &values[i]);
        qsort (values, N, sizeof (int), compareints);
        printf("%d", values[0]);
        for(i = 1; i < N; i++)
            printf(" %d", values[i]);
        printf("\n");
    }
    return 0;
}

Remember not post solutions. Your post may be reviewed by our moderators.

  • Andre Marasca replied 2 years ago

    Muito obrigado FEODORV! Consegui arrumar, eu não tinha percebido o intervalo de h, muito útil sua dica!

  • feodorv replied 2 years ago

            qsort (values, N, sizeof (int), compareints);

    Sorting 3M numbers by qsort takes a lot of time. But do you really need qsort? Hint: 20 ≤ h ≤ 230 and counting sort https://medium.com/basecs/counting-linearly-with-counting-sort-cd8516ae09b3