Linhas Cruzadas - Fórum

• 
  marcoscosta em

  04 de Mar de 2016

  O que tem de errado no meu código que só não passa nos casos de teste que estão no problema?? (ps: eu testei e passou na minha maquina)

• 
  marcoscosta em

  04 de Mar de 2016

  #include <stdio.h>

  #include <string.h>

   

  int main() {

      int n, x, i, j;

      int nums[60001] = {0};

      scanf("%d", &n);

      for (i = 0; i < n; ++i) {

          scanf("%d", &x);

          nums[x] = i;

      }

      int cruzados = 0;

      for (i = 1; i <= n; ++i) {

          for (j = i-1; j >= 1; --j) {

              if (nums[j] > nums[i]) {

                  cruzados++;

              }

          }

      }

      printf("%d\n", cruzados);

  return 0;

  }

   

• 
  Erich Rodrigues em

  04 de Mar de 2016

  Fala Marcos, você está usando uma abordagem que não vai passar em todos os casos de teste por conta da complexidade (N²). Tente pensar em uma outra abordagem ou em alguma estrutura de dados que resolva esse problema.