Блог пользователя Nagasai74

Why is this TLE??
Автор Nagasai74, история, 3 года назад, По-английски

Hello Everyone !!

1535B - Переупорядочение массива

118383036

Can Someone explain me why this solution gave TLE Verdict ??

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

TLE is time limit exceeded. Which simply means make your code more efficient.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I agree, But I wanted to know which part in my code is causing such inefficiency!!

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think (a[j]<<1) part it is not required actually u can simply check __gcd(a[i],2*a[j])> 1 || __gcd(2*a[i],a[j])>1 then count++

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, you are right That works But (a[j]<<1) is equal to a[j]*2 and is faster, That should not cause TLE Right??

        → Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Maybe it's yours overloaded sort, try this, maybe it'll help: Also yours output is empty maybe infinite loop

for (int i = 0, j = n - 1; i < j;) {
    if (v[i] % 2 and v[j] % 2 == 0) {
      swap(v[i], v[j]);
      ++i;
      --j;
    } else if (v[i] % 2 == 0 and v[j] % 2) {
      ++i;
      --j;
    } else if (v[j] % 2 == 1) {
      --j;
    } else if (v[i] % 2 == 0) {
      ++i;
    }
  }
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    when sorting if compare function have 2 odd or 2 even numbers it's output will give different

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Your comparator is wrong, it has to implement strict weak ordering, which essentially means that comparator should return true if you for sure want first element before second and false in any other case (including if you don't care about order)

The correct comparator would be

sort(a, a + n, [&](int a, int b){
    if ((a & 1) == (b & 1)) return false;
    if(a & 1) return false ;
    return true ;
}) ;
→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

All you should know about comparator in C++

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Your comparator function is wrong .... You may have simply used greater()

→ Ответить