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

Change in Mo's algo sort function gives different results
Автор kishore_p, история, 6 лет назад, По-английски

I used Mo's algo to solve this problem .

First compare function: It gives me wrong answer Submission1

bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 if(x&1)
 return (a.R > b.R);
 else
 return (a.R < b.R);
}

Second function : Gives me AC Submission2

bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 else
 return a.R < b.R;
}

First one is an optimisation,but not able to find why it gives wrong answer

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

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

In the first code, as you go backwards(going from (L1, R1) to some (L2, R2) such that L2 < L1 and R2 < L1) you will call dec on an element that has not yet been added. In order to avoid this, you should first increase the size of segment you're on, and then dec, i.e. first call inc(++right) and inc(--left) and then dec(left++) and dec(right--).

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the reply. It is clear now . Any sort function try to inc the range first and then dec.

    So if I interchange less than and greater than as below. inc,inc,dec,dec will still work

    bool comp(query &a,query &b)
{
 int x=a.L/bsize;
 int y=b.L/bsize;
 
 if(x!=y)
 return x<y;
 if(x&1)
 return (a.R < b.R);
 else
 return (a.R > b.R);
}
    → Ответить