Unusual Runtime Error when performing Mo's Algorithm in C++

Правка en2, от YMSeah, 2023-12-11 04:48:12

I ran into a runtime error when trying to solve 1514D - Cut and Stick with Mo's Algorithm. Part of the problem requires one to find the counts of an element within a range if it's greater than or equal to about half the counts of elements in the range. One way to solve it is to use Mo's Algorithm to keep track of the most common element in range and its counts.

I sort the queries in the standard way where the left boundaries are grouped together in blocks of about sqrt of the number of elements. Within a "left block", the right queries are sorted in increasing order if the "left block" is an even block, otherwise it is sorted in decreasing order (so that the right points zigzag left-right-left-right through alternating blocks).

I have found that using the following within the sort criterion gives a runtime error (235446182):

if (block1 == block2) {
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks
    if (block1% 2 == 0 && r < other.r) {
        return true;
    }
    if (block1 % 2 == 1 && r >= other.r) {
        return true;
    }
}

and the following does not (235448205).

if (block1 == block2) {
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks
    if (block1% 2 == 0 && r < other.r) {
        return true;
    }
    // if (block1 % 2 == 1 && r >= other.r) { // This gives run time error
    if (block1 % 2 == 1 && r > other.r) {
        return true;
    }
}

I also see that I am not the only person who faced this problem. Here are nawa's codes and his fix using a similar change: runtime error 129082770 vs accepted 129084946.

I am not a native C++ user and I cannot figure out what went wrong. I will be grateful if anyone can shed some light on what may have caused this error.

Теги mos algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский YMSeah 2023-12-11 05:37:03 9
en2 Английский YMSeah 2023-12-11 04:48:12 239 (published)
en1 Английский YMSeah 2023-12-11 04:41:17 1965 Initial revision (saved to drafts)