Проверьте, что a+b==c. Самый короткий способ: cout << "-+"[a+b==c] << '\n';

Ссылка на AC сабмит

Разместите чётные конфеты все до нечётных. Выяснится, что самое последнее сравнение будет "сумма всех чётных" минус "сумма всех нечётных" и можно проверить именно его результат. Остальные более благоприятные для нас и их можно не проверять.

Ссылка на AC сабмит

У нас есть всего две чередующиеся бинарные строки длины n: одна начинается с $$$0$$$, вторая начинается с $$$1$$$, то есть $$$01010101...$$$ или $$$101010101...$$$ Проверим каждую.

По условию задачи, мы каждой латинской букве сопоставляем $$$0$$$ ИЛИ $$$1$$$. Давайте проверим каждую букву. Если есть такое, что одна и та же буква должна перейти в $$$0$$$ в какой-то позиции и в $$$1$$$ в какой-то другой позиции, то ответ No. Если ни одной такой буквы нет, то ответ Yes.

Проверку можно провести следующим образом. Заведём map<char,int> — какую цифру мы сопоставим каждой букве. При проверке позиции i проверяем, есть ли буква s[i] в мапе как ключ (сопоставили ей что-то или нет). Можно через map.find или map.count или map.contains. Если нет, то сопоставляем, иначе она есть и это будет означать, что она уже встретилась раньше. Проверим, что до этого мы сопоставили ровно то, что хотим сопоставить сейчас. То есть, если мы хотим $$$1$$$, то в мапе лежит именно $$$1$$$, а не ноль.

Ссылка на AC сабмит

Построим префикс суммы поверх массива. Теперь умеем считать сумму на любом отрезке за $$$O(1)$$$. Обрабатывать запрос за $$$O(1)$$$ можно следующим образом: возьмём предподсчитанную сумму всех чисел $$$S$$$, вычтем из него (pref[r] - pref[l-1]) и прибавим (r-l+1LL)*k. Именно так изменится сумма после замены подотрезка. Если получилось нечётное число, то ответ Yes, иначе No.

Ссылка на AC сабмит

Изначально в любой кучке может быть загаданный камень, то есть, кандидаты {1,2,3,...,n}. Давайте делить множество кандидатов пополам (на две группы примерно равной длины). Например, все кандидаты на чётной позиции массива относим в первую группу, а нечётной — во вторую группу.

Тогда мы можем спросить сумму в первой группы: какая она? Нам сообщат число. Давайте проверим, что оно реально сумма в этой группе (мы же знаем индексы). Если всё совпало (оказалось, что в первой группе нет нашего камня), то ответ режит во второй группе, иначе ответ лежит в первой группе.

Таким образом, на каждой итерации мы уменьшаем множество подходящих ответов вдвое, пока оно не станет содержать ровно один элемент. Его мы и выводим в качестве ответа.

Ссылка на AC сабмит

Суммарное количество клеток поля, по условию, n * m <= 5 * 10^4. Это $$$50$$$ тысяч клеток. В каждой клетке мы можем находиться в четырёх состояниях (в зависимости от текущего направления). Получается, у нас $$$50000 \times 4$$$ состояний в худшем случае и мы между ними переходим.

Можем промоделировать явно, начиная со стартового состояния, пока не придём в искомую точку.

На каждой итерации, если мы уже в искомой точке, то сразу сообщаем ответ и заканчиваем моделирование, иначе надо сделать шаг.

Посещённые состояния будем хранить в виде четвёрки чисел (строка, столбец, смещение вверх, смещение вправо). Можем заносить их в std::set. Если в некоторое состояние мы пришли повторно, то завершаем моделирование процесса.

Отскок проверяем так: если вышли за пределы карты (по строкам и столбцам отдельно), то возвращаемся и смещение меняем на противоположное (по строкам и столбцам отдельно) и делаем шаг в изменённом направлении.

Получается $$$O(n \cdot m \cdot \log{n\cdot m})$$$.

Ссылка на AC сабмит

Будем набирать элементы в порядке их неубывания (сортим вектор $$$c$$$). У нас уже есть {1}, поэтому, если c.front() > 1, то ответ сразу No, иначе набираем элементы начиная со второго.

Элементы c[i] до $$$200000$$$. То есть, наша сумма подпоследовательности до $$$200000$$$. Давайте хранить все возможные суммы — их всего-то $$$200000$$$. Где хранить?

Давайте заведём битсет на $$$200200$$$ элементов, где bitset[s] = 1, если подпоследовательность с данной суммой s уже есть, иначе $$$0$$$. Изначально только bitset[1] = 1.

Итак, пусть мы хотим набрать c[i] для каждого $$$i$$$ от $$$2$$$ до $$$n$$$. Сперва проверим, можем мы его набрать или нет. То есть, bitset[c[i]] равен $$$1$$$ или нет. Если не можем, то ответ No, иначе можем набрать, набираем (добавляя в наш массив $$$a$$$). У нас появился новый элемент в векторе $$$a$$$, равный c[i]. Давайте обновим все возможные подпоследовательности. У нас уже они были без учёта этого элемента. Теперь в каждую из них мы можем добавить c[i] или оставить без изменений. То есть, bitset |= (bitset << c[i]) — обновление множества подпоследовательностей за $$$O\left(\frac{n}{32}\right)$$$.

Итого, получили решение за $$$O\left(\frac{n^2}{32}\right)$$$. Оно работает за 800 мс (с запасом в $$$2.5$$$ раза).

Ссылка на AC сабмит