NEED HELP: WA - Codeforces

→ Обратите внимание

До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

NEED HELP: WA

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

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

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

help, wa

simp_pro
2 года назад
15

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

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

systy

2 года назад, # |

← 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

2 года назад, # ^ |

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

2 года назад, # ^ |

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

2 года назад, # ^ |

← 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

2 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

simp_pro

2 года назад, # ^ |

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

→ Ответить

systy

2 года назад, # ^ |

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.

→ Ответить