Zadanie Unikaty z main.edu.pl

Odpowiedz Nowy wątek
2011-07-16 14:33
0

Witam.
Zrobiłem zadanie unikaty z main.edu.pl: http://main.edu.pl/pl/user.ph[...]task&task=uni&con=ALG
Niestety dostaję za to zadanie 90 punktów i proszę o pomoc, ponieważ nie mam pojęcia jak ulepszyć program, aby dostawał 100 punktów.
Nie przechodzi jednego testu, przy czym wyskakuje w ramce wynik: błąd wykonania, a niżej informacja: memory limit exceeded kod wyjścia: 1.

Oto kod programu:

#include<cstdio>
 
int a[20000], b[20000]; // tworze dwie tablica
 
void merge(int *a, int *b, int p, int q, int r) // scalanie tablic
{
    int i = p;
    int j = q + 1;
    int k = p;
 
    while(i <= q && j <= r)
    {
        if(a[i]<a[j])
        {
            b[k] = a[i];
            i++;
        }
        else
        {
            b[k] = a[j];
            j++;
        }
        k++;
    }
 
    while(i <= q)
    {
        b[k] = a[i];
        i++;
        k++;
    }
 
    while(j <= r)
    {
        b[k] = a[j];
        j++;
        k++;
    }
 
    for (int c = p; c <= r; c++) // przepisuje tablice a do tablicy b
        a[c] = b[c];
}
 
void mergesort(int *a, int *b, int p, int r) // funkcja sortujaca
{
    if(p!=r)
    {
        int q=(p+r)/2;
        mergesort(a, b, p, q);
        mergesort(a, b, q+1, r);
        merge(a, b, p, q, r);
    }
}
 
int main()
{
 
    int n;
 
    scanf("%d", &n);
 
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
 
    mergesort(a, b, 0, n-1); // sortowanie ciagu przez scalanie
 
    int w=1;
 
    for(int i=1; i<n; i++)    // zliczam ilosc liczb, ktore wytapily
    {
        if(a[i] != a[i-1])
          w++;
    }
 
    printf("%d", w);
 
    return 0;
}
 
edytowany 1x, ostatnio: JumpSmerf, 2011-07-16 14:34

Pozostało 580 znaków

2011-07-16 15:00
0

Zamiast mergesort zrób to przy pomocy unordered_set z tr1.

cytuję zadanie: " Zadaniem Twojego programu jest obliczenie ile różnych liczb występuje w tym ciągu. Wykorzystaj w tym zadaniu algorytm mergesort." Skoro każą to IMO powinien użyć mergesorta, chociaż wiadomo, że ich sprawdzaczka tego nie sprawdza. - piternet 2011-07-16 16:24

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0