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

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

Hello Everyone !!

1535B - Array Reodering

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 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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