Nagasai74's blog

Why is this TLE??
By Nagasai74, history, 3 years ago, In English

Hello Everyone !!

1535B - Array Reodering

118383036

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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++

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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??

        → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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;
    }
  }
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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 ;
}) ;
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

All you should know about comparator in C++

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply