Codeforces Global Round 3 |
---|
Закончено |
Вам дано $$$n$$$ объектов. У каждого объекта есть два целочисленных свойства: $$$val_i$$$ — его цена — и $$$mask_i$$$. Гарантируется, что изначально сумма цен всех объектов не равна нулю.
Вы хотите выбрать некоторое целое положительное число $$$s$$$. После этого все объекты модифицируется, причем $$$i$$$-й объект модифицируется следующим образом:
Нужно найти такое целое число $$$s$$$, что если произвести модификацию, как описано выше, то сумма всех цен сменит знак (если она была отрицательной, то она должна стать положительной, и наоборот; не разрешается сумме становится нулём). При этом абсолютное значение суммы цен может стать любым.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) — количество объектов.
$$$i$$$-я из следующих $$$n$$$ строк содержит целые числа $$$val_i$$$ и $$$mask_i$$$ ($$$-10^9 \leq val_i \leq 10^9$$$, $$$1 \le mask_i \le 2^{62} - 1$$$) — цена объекта и его маска.
Гарантируется, что сумма всех $$$val_i$$$ не равна нулю.
Выведите целое число $$$s$$$ ($$$1 \le s \le 2^{62} - 1$$$) такое, что если его произвести модификацию, как описано выше, то сумма всех $$$val_i$$$ сменит знак.
В случае если существует несколько таких $$$s$$$, выведите любое из них. Можно показать, что всегда существует хотя бы одно подходящее $$$s$$$.
5 17 206 -6 117 -2 151 9 93 6 117
64
1 1 1
1
В первом тестовом примере все объекты изменят свою стоимость кроме объекта с маской $$$151$$$.
Поэтому их сумма изменит знак: изначально $$$24$$$, после модификаций — $$$-28$$$.
Во втором тестовом примере единственный объект поменяет свою стоимость. Поэтому сумма всех цен изменит знак.
Название |
---|