Zadanie z MAIN2 – przekroczenie limitu czasowego w ostatnim teście

Mam problem a mianowicie robię zadanie z portalu MAIN2 https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/akc/ . Program działa wszystko poprawnie, tylko w ostatnim teście jest przekroczenie limitu czasowego i nie wiem jak na to zaradzić i jak można napisać ten program żeby ten algorytm działał jeszcze szybciej.

#include <iostream>
using namespace std;

int minimum (int wartosc, int czastka[], int n){
    int poczatek = 0;
    int srodek;
    int koniec = n - 1;
    int minimum_dodatnie = -1;
    while (poczatek < koniec){
        srodek = (poczatek + koniec) / 2;
        if (czastka[srodek] >= wartosc)
            koniec = srodek;
        else
            poczatek = srodek + 1;
    }
    if (czastka[poczatek] == wartosc)
        return poczatek + 1;
    return 0;
}

int maximum (int wartosc, int czastka[], int n){
    int poczatek = 0;
    int srodek;
    int koniec = n - 1;
    int maximum_dodatnie = -1;
    while (poczatek < koniec){
        srodek = (poczatek + koniec + 1) / 2;
        if (czastka[srodek] <= wartosc)
            poczatek = srodek;
        else
            koniec = srodek - 1;
    }
    if (czastka[koniec] == wartosc)
        return koniec + 1;
    return -1;
}

int main() {
    int n;
    cin >> n;
    int czastka[n];
    for (int i = 0; i < n; ++i)
        cin >> czastka[i];
    int q;
    cin >> q;
    int wartosc[q];
    for (int i = 0; i < q; ++i)
        cin >> wartosc[i];
    for (int i = 0; i < q; ++i){
        int minimum_na_plusie;
        int maximum_na_plusie = -1;
        minimum_na_plusie = minimum(wartosc[i], czastka, n);
        if (minimum_na_plusie)
            maximum_na_plusie = maximum(wartosc[i], czastka, n);
        int ilosc = maximum_na_plusie - minimum_na_plusie + 1;
        cout << ilosc << endl;
    }
}

1. Być może masz jakiś błąd w implementacji. W bibliotece standardowej C++ są funkcje lower_bound i upper_bound, które robią bisekcję znajdując początek i koniec przedzialu (tylko operują na przedziale otwartym z prawej strony), oraz funkcja equal_range, która za 1 wywołaniem zwraca obie wartości zakresu. Możesz je sprawdzić. Jeżeli zadziała, to znaczy, że problem leży w Twoje implementacji wyszukiwania binarnego.

2. Wyłącz synchronizację ze strumieniami wyjściowymi z biblioteki standardowej C - https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

3. int czastka[n]; i int wartosc[q]; stworzone na stosie to niepoprawny kod c++ (w przeciwieństwie do C, od C11), który kompilator mimo wszystko łyka. Dodatkowo, ponieważ te zmienne istnieją na stosie wywołań funkcji to możesz dojść do przepełnienia, jeżeli stos byłby zbyt mały. Użyj std::vector albo stwórz globalną tablicę o maksymalnym rozmiarze danych.

4. Zamiast wyszukiwania binarnego można użyć tablicy hashującej do zliczania wartości - std::unordered_map.

Ale ja jestem początkującym i się dopiero uczę także wolę korzystać z tego wyszukiwania binarnego. Mam inny kod z internetu tylko wydaje mi się że wszystko działa na podobnej zasadzie a algorytm wykonuje się średnio 4 razy dłużej. Gdzie jest ta różnica. To jest kod źródłowy z internetu:

#include <cstdio>
#include <stdlib.h>
 
using namespace std;
 
int firstOccurence(int* data, int length, int element)
{
        int start = 0, end = length - 1;
        int looked = -1;
        while (start < end)
        {
                looked = (start + end) / 2;
                if (data[looked] >= element)
                {
                        end = looked;
                }
                if (data[looked] < element)
                {
                        start = looked + 1;
                }
 
        }
        if (data[start] == element)
        {
                //znalazlem liczbe - pierwsze wystąpienie
                return start;
        }
        return -1; //nie znaleziono
}
 
int lastOccurence(int* data, int length, int element)
{
        int start = 0, end = length - 1;
        int looked = -1;
        while (start < end)
        {
                looked = (start + end + 1) / 2;
                if (data[looked] <= element)
                {
                        start = looked;
                }
                if (data[looked] > element)
                {
                        end = looked - 1;
                }
 
 
        }
        if (data[end] == element)
        {
                //znalazlem liczbe - ostatnie wystąpienie
                return end;
        }
        return -1; //nie znaleziono
}
 
int binarySearch(int* data, int length, int lookNumber)
{
        if (length == 1)
                return data[0] == lookNumber ? 1 : 0;
        if (length == 0)
                return 0;
        int first = firstOccurence(data, length, lookNumber);
        if (first >= 0)
        {
                int last = lastOccurence(data, length, lookNumber);
                return last - first + 1;
        }
        else
                return 0;
}
 
int main()
{
        int length;
        scanf("%d", &length);
        int* results = new int[length];
        for (int i = 0; i < length; i++)
                scanf("%d", &(results[i]));
        //ciag zebrany
 
        long long queryCount;
        scanf("%lld", &queryCount);
 
        int* queries = new int[queryCount];
 
        for (long long i = 0; i < queryCount; i++)
                scanf("%d", &(queries[i]));
 
        //dane zebrane
        //teraz sprawdzamy
        for (long long queryNdx = 0; queryNdx < queryCount; queryNdx++)
        {
                // dla każdego zapytania przeszukuj binarnie
                int output = binarySearch(results, length, queries[queryNdx]);
                printf("%d\n", output);
                //cout << binarySearch(results, length, queries[queryNdx]) << endl;
        }
 
        return 0;
}

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::map<int, int> hist;// zmiana na unordered_map poprawi złożoność 
              // z o(log(n) * q + n * log(n)) na o(q + n)
    int n, q, x;
    std::cin >> n;
    for (int i=0; i<n; ++i) {
        std::cin >> x;
        ++hist[x]; // złożoność o(log(n)) dla zwykłej map-y
    }
    cin >> q;
    for (int i=0; i<q; ++i) {
        std::cin >> x;
        std::cout << hist[x] << '\n';// złożoność o(log(n)) dla zwykłej map-y
    }

    return 0;
}

Dane wejściowe nie muszą być posortowane.
Można jeszcze poprawić, by nie wstawiało nadmiarowych danych do hist, ale nie będę mącił.

Edit: A może jednak nieco namącę

MarekR22 napisał(a):

Dane wejściowe nie muszą być posortowane.

Jak w zadaniu stoi jak byk, że są w kolejności niemalejącej, to jednak są posortowane :)

Moim zdaniem w pierwszym programie źle ustawiasz początek przy maksimum, dajesz zero a powinna być pozycja minimum. W końcu wiadomo już że wcześniej nie będzie.