Themis BINSRCH problem z scanf()

Question

Cześć wszystkim. Mam do zrobienia zadanie BINSRCH z  https://themis.lo14.wroc.pl

Zadanie udało mi się rozwiązać na wyjściu cout i cin lecz sędzia online w ostatnim teście pokazuje "time limit exceeded". Ograniczenie to 4s wykonania. Powiedziałem sobie no cóż, trzeba wymysleć coś innego i usłyszałem o scanf() i printf() że są szybsze i będzie lepiej. No to ich użyłem lecz teraz problemem jest to że przy wpisywaniu wartości do drugiej tablicy i potem ich odczytaniu.. no kurde są dziwne, jakbym wychodził poza tablicę czy coś, lub przez białe znaki.

-szukałem pomocy u googla z marnym skutkiem.

-próbowałem czyszczenie bufora ale marny skutek, chyba że robiłem to źle (flfush(stdin);)

Czy ktoś jest w stanie mi to wytłumaczyć i pomóc przy tym?

 

EDIT: zrobiłem edit kodu, jest prawie dobrze. Ostatnia wartość na wyniku się nie zgadza.

Np: (najpierw wielksoc tablicy[ENTER] trzy wartosci po spacjach i potem drugi raz to samo ilośc testow i trzy wartosci po spacji. Na końcu wynik.

3

3 3 3

3

1 1 1

wynik: 3 3 2 a powinno być 3 3 3

---

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

using namespace std;

int main() {
    
    int i=0, n, N;
    /*
    cin>>n;
    int tabn[n];
    for(int i=0;i<n;i++){
        cin>>tabn[i];
    }
    
    cin>>N;
    int tabN[N];
    for(int i=0;i<N;i++){
        cin>>tabN[i];
    }
    */
    
    
    scanf(" %d",&n);
    unsigned int tabn[n];
    for( int i = 0; i < n; i++ )
    {
        scanf( " %c", & tabn[ i ] );
    }
    
    
  
    scanf(" %d", &N);
    unsigned int tabN[N];
    for( int i = 0; i < N; i++ )
    {
        scanf( " %c", & tabN[ i ] );
    }
    
        
    int tabW[N];
    for(int i=0;i<N;i++){
        int zap=tabN[i];
        int count=0;
            for(int j=0;j<n;j++){
                if(zap<=tabn[j]) count++;
            }
        tabW[i]=count;    
        }
    
    for(int i=0;i<N;i++){
        cout<<tabW[i]<<" ";
        
    }
    
    
    
}

 

Comments

A jesteś pewien że to nie jest problem z algorytmem?

---

Robiłem różnorakie testy. Zamieniałem miejscami kolejność wpisywania tablic. Zawsze druga tablica ma złe wartości. podam jej np. 3 3 3 a ona wyswietli 0 1 -123124124.

Raz mi się prawie udało gdy dodałem spacje przy scanf() a dokłądnie w miejscu   " %d"(wcześniej "%d"). Przy wpisaniu wartosci np. 1 1 1 wyswietlało 3 1 1. pierwsza trojka to zapewnie łapie wczesniejszy scanf() tak mi się wydaje czy coś.

---

Jeśli poznam dokładną treść zadania postaram się pomóc. Via prv proszę.

---

Wrzucam publicznie. Może ktoś się znajdzie. Na Cout<<, cin>> program mi działa i sędzia nawet go puszcza ale na ostatnie próbie przekracza 4s i wurzuca "time limit exceeded"

 

---

1. Wskaż gdzie w swoim kodzie używasz wyszukiwania binarnego? Szukasz liniowo a dane są posortowane więc szybsze będzie wyszukiwanie binarne.

2. Zła alokacja tablicy. W C++ nie używamy VLA.

3. Nawet jeśli używasz nagłówków z C w programie C++, to odpowiednikiem <stdio.h> jest <cstdio>. W tym programie jednak nie będzie potrzebne używanie takiego wejścia.

4. Lepiej użyć std::vector niż walczyć z tablicą i jej usunięciem.

Wczytanie danych do std::vector:

#include <iostream>
#include <vector>
#include <cstddef>

int main() {
    std::size_t n;
    std::cin >> n;
    // Zakładając że int ma 32-bity
    std::vector<unsigned> data;
    data.reserve(n);
    for(std::size_t i = 0; i < n; ++i) {
        std::cin >> data[i];
    }
}

Zgodne z C++03 bo nie wiem jaki kompilator ma sędzia.