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

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

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

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

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

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)