reaper28's blog

WA on 2nd test case please help(https://mirror.codeforces.com/problemset/problem/1256/B)

By reaper28, history, 5 years ago, In English

question link : https://mirror.codeforces.com/problemset/problem/1256/B solution link : https://ideone.com/JInG1y What is the problem in this anyone?

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

could you elaborate on how your code is supposed to work ??

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    start from 1 if in correct position continue otherwise found its position and while its not in its correct position and swap is possible i keep on swapping.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

more specifically what is the map <ll, ll> h doing ??

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

consider the test case: 1 8 8 5 6 7 1 3 2 4

you code gives: 1 8 5 6 2 7 4 3

ans 1 8 5 6 2 7 3 4

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Your code is swapping them before assigning right cnt, swap(a[e],a[e-1]); cnt[a[e]]=e-1; cnt[a[e-1]]=e; First update then swap cnt[a[e]]=e-1;cnt[a[e-1]]=e;swap(a[e],a[e-1]); then second thing if say a[e] is 4 and a[e-1] is 3, then you should not swap... eg take this case: n=8, arr=[8 5 6 7 1 3 2 4] after some steps it becomes 1 8 5 6 2 7 3 4, we cannot swap 3 with 7 as that operation is already used, then your code is swapping 4 with 3, hence it gives 1 8 5 6 2 7 4 3. add a condition while(e>i && a[e-1]>a[e] && h.count(e-1)==0)

→ Reply