NEED HELP: WA - Codeforces

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

До соревнования
Educational Codeforces Round 189 (Rated for Div. 2)
4 дня
Зарегистрироваться »

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

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

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

Всё →

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

№	Пользователь	Вклад
1	Qingyu	157
2	adamant	153
3	Um_nik	147
3	Proof_by_QED	147
5	Dominater069	145
6	errorgorn	142
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Всё →

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

→ Прямой эфир

Детальнее →

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

NEED HELP: WA

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

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

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

help, wa

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

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

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

systy

4 года назад, скрыть # |

← 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

4 года назад, скрыть # ^ |

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

4 года назад, скрыть # ^ |

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

4 года назад, скрыть # ^ |

← 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

4 года назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

simp_pro

4 года назад, скрыть # ^ |

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

→ Ответить

systy

4 года назад, скрыть # ^ |

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.

→ Ответить