Travis_Bickle's blog

Why this code gets MLE
By Travis_Bickle, history, 4 years ago, In English

Problem: https://mirror.codeforces.com/contest/1156/problem/B

Code: https://www.ideone.com/v5gzlN

I tried finding why this code could get MLE but failed however I think the error could be in the while loop in a certain case it keeps adding to the string until there is MLE so correct me if I am wrong

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

The below condition evaluates to $$$true$$$ in case $$$c.size()$$$ is less than or equal to $$$1$$$, because $$$c.size()$$$ is unsigned, and in this case $$$c.size() / 2 - 1 = -1$$$ and the $$$-1$$$ treated as unsigned is a large value causing the evaluation to be $$$true$$$.

if(c.size() / 2 - 1 >= 0)

And that causes an out-of-boundary access to vector $$$c$$$, which eventually causes an out-of-boundary access to vector $$$fa$$$ inside the function "print" below, and that would cause a large string to be allocated in case the out-of-boundary access to $$$fa$$$ happens to be a large value.

void print(string s1, const vector<int> &fa){
    for(const auto&i : s1){
        cout << string(fa[i - 'a'], i);
    }
    cout << "\n";
}

The code is accepted after adding cast to int (156966101)

→ Reply