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

Автор WRKRW, история, 8 месяцев назад, По-английски

In 225165101,the length of array a and b is smaller than 2500.However,it doesn't get RE,but get MLE.Why? Problem: 1882E1 - Две перестановки (простая версия)

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

»
8 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

You have:

for(int i=1;i<=m;i++){
    while(b[i]!=i){
        swa(i,b[i],m,q);
        int t=b[i];
        swap(b[i],b[t]);
    }
}

For $$$i > 2002$$$, there's some garbage at b[i] and b[t] = b[b[i]], so b[i] != i will almost certainly be true.

So, the while loop runs indefinitely, and swa() appends to q $$$3$$$ times, which leads to MLE.