NEED HELP: WA - Codeforces

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:50:22
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

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

Всё →

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

→ Прямой эфир

Детальнее →

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

NEED HELP: WA

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

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

Submission link: https://mirror.codeforces.com/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.

→ Ответить