TÓPICO

TLE, COMO ASSIM?

Fernando Morato perguntou 1 ano atrás

include <bits/stdc++.h>

using namespace std;

int n, q, x, m; vector v;

int busca(int ini, int fim, int num){

int meio = (ini+fim)/2;

while(ini <= fim){ if(meio == num) return meio; else if(meio > num) fim = meio-1; else if(meio < num) ini = meio+1; } return 0; }

int main() {

while(scanf("%d %d", &n, &q), (n && q)){

for(int i = 0; i < n; i++){
  scanf("%d", &x);
  v.push_back(x);
}

sort(v.begin(), v.end());
n = v.size();

for(int i = 1; i <= q; i++){
  printf("CASE #%d:\n", i);
  scanf("%d", &x);
  m = busca(0, n, x);
  if(m != 0){
    printf("%d found at %d\n", x, m);
  }else{
    printf("%d not found\n", x);
  }
}

}

}

Este tópico foi resolvido e não pode receber novas respostas.

  • [py] self.luis respondido 1 ano atrás

    Você deve fazer a ordenação quicksort, devido a sua complexidade ser menor, O(n * long(n)), e uma busca linear, por isso o time da questão é 2, devido a necessidade da busca linear, note que os valores podem ser repetidos, e para casos como:

    10 2
    1
    1
    2
    2
    3
    3
    5
    5
    4
    4
    4
    5
    0 0

    A busca binaria falha.