NEED HELP: WA - Codeforces

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

NEED HELP: WA

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

Problem link: https://codeforces.com/contest/1472/problem/E

Submission link: https://codeforces.com/contest/1472/submission/165709605

help, wa

simp_pro
22 месяца назад
15

Комментарии (13)

Показать архивные | Написать комментарий?

systy

22 месяца назад, # |

← Rev. 4 →

I can't really understand what's the purpose of cj. a[i] != a[i - 1] is always true, because all pairs in a also contain their index in initial array.

→ Ответить

systy

22 месяца назад, # ^ |

Probably got its meaning. You need to check if a[i].fi.fi != a[i - 1].fi.fi and also you don't need to always update cj. You also need to check if a[cj].fi.se > a[ci].fi.se when updating. I changed it in your code and it got accepted.

165772947

→ Ответить

simp_pro

22 месяца назад, # ^ |

Why is this necessary? ci is always containing the least value so we can directly update cj to ci if we can. Can you provide some test case or argument why was this necessary?

→ Ответить

systy

22 месяца назад, # ^ |

← Rev. 3 →

First of all, I need to ask you smth. Am I right, that cj contains the index of the smallest by width box that has height which is less (not less or equal, but less) than the current? (if we sort our boxes by height).

→ Ответить

systy

22 месяца назад, # ^ |

← Rev. 2 →

Yup, you are right, my bad. Checking whether ci is better than cj is not necessary.

→ Ответить

simp_pro

22 месяца назад, # ^ |

Yes, that's the correct meaning of cj. But why is your code giving AC but mine is giving WA?

→ Ответить

systy

22 месяца назад, # ^ |

The point is that, as I said, that you are not really checking what you want. a[i] != a[i - 1] is always true, as a[i] is a tuple {h, w, id} and id is unique for every a[i]. You need to check that a[i - 1].h != a[i].h. I changed got so it does (and also added useless check a[cj].fi.se > a[ci].fi.se) and it got accepted.

→ Ответить