Блог пользователя Mr.obeidat

Автор Mr.obeidat, история, 11 лет назад, По-английски

Hello everyone. how i could avoid time limit exceeded in this problem E.Time Limit Exceeded? http://codeforces.me/gym/100676

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

»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hello...

This problem solvable using Binary Search, but you need to edit something in the algorithm.

1- read the input.

2- sort the sequence.

3- initialize answer = 0.

4- For i=0 to n do:   
       s = i;    // start
       e = n-1;  // end
       res=i;
       While s<=e do:         // binary search
            m = (e+s)/2;      // mid
            if(abs(x[i]-x[m])>31)   // if the difference more than 31.
                e = m - 1;
            else{   // so we found element with difference less than or equal to 31.
                 s = m + 1;
                 res=m;  // save it!!
                }
       endWhile   
       answer += res-i; // add the distance between the desired element and the current location.
       endFor

5- print the answer.

// hope this helped you. ^_^