Wataru

Сначала напишите алгоритм на каком-нибудь высоком языке программирования, или хотя бы в псевдокоде. Потом аккуратно переведите в ассемблер.

Надо уметь только делить с остатком и умножать на 10. Как перевести 1234 в строку? Можно взять последнюю цифру - осток от деления на 10. Вот вы получили цифру 4. В строке это будет символ "4", или байт со значением 0x34. Вообще, для получения символа по цифре - надо прибавить 0x30. Это мы взяли остаток, а вот результат деления - 123. Можно продолжить перевод так же и мы получим символы в обратном порядке.

Итак, пока число не 0, делим нацело на 10. Остаток приписываем в ответ переводя в символ. В конце разворачиваем строку.

Перевод же из строки в число делается проще - идем циклом по строке, умножаем переменную на 10 и прибавляем тукущую цифру.

Потому что тут разное поведение.

Первый вариант отбрасывает дробные части от копеек, а второй отбрасывает дробные части от рублей. Ведь при делении на 100 в целых числах идет округление вниз. Если брать p процентов с округлением вниз от числа в рублях, то и получится целое число в рублях. Если брать от числа в копейках, то и получится целое число в копейках.

Поскольку второй код отбрасывает все копейки при прибавлении, то ему требуется больше итераций, чтобы дойти до y. На самом деле он может даже виснуть, если там получается прибавление 0.

Быстрое преобразование Фурье - это алгоритм вычисления дискретного преобразования фурье. От интеграллов на картинках оно отличается тем, что там не функция от которой береться интеграл, а массив данных, которые как-то суммируются. Оно называется быстрым, потому что там идет вычисление не в лоб по формуле из википедии, а чуть хитрее, за счет чего оно работает быстрее.

В компьютерах используется дискретное преобразование, потому что ну не могут компьютеры работать с бесконечным неприрывным объектом, коим является функция.

И да, там результат - это массив комплексных чисел, поэтому выходные данные в 2 раза больше входных, которые являются вещественными.

Проще "отсортировать" заданные координаты. Если x1 > x2, поменяйте их местами. То же с z1 и z2, А потом остается только первый случай в вашем коде.

Это сильно короче писать и легче читать и понимать. В ваших четырех копипастах очень легко где-то допустить ошибку и очень тяжело ее потом найти.

Константа вылезает из деталей реализации операций. Вот сортировка пузырьком делает ровно n(n-1)/2 сравнения и помен в худшем случае. Еще столько же операций инкремента счетчика индекса, столько же проверок на конец цикла. Плюс еще n операций для внешнего цикла. И все это O(n^2). Хотя там есть есть /2 и операций четыре типа. И они еще разное время занимают. Скажем, проверки занимают 10 тактов, а инкрименты - 1. Но вся эта мишура не влияет на скорость роста и прячется в константе. Если все сложить. То будет C*n^2 +C2*n+C3 тактов на алгоритм.

Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.

Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.

Но если так хотите - то делается это так: Сначала пройдитесь по всем клеткам и занумеруйте те, которые не являются коридором (один сосед, больше двух соседей, или соседи не вдоль одной прямой). Можно в отдельной матрице номера проставить.
Потом пройдитесь по каждому столбцу сверху вниз и по каждой строчке слева направо и храните последнюю встреченную вершину. Если встретили стену - забывайте про эту увиденную раньше врешину. Если встретили просто проход - пропускайте его. Если встретили поворот(вершину) - то создайте ребро между ней и последней увиденной (если она еще в памяти, ведь стена могла ее удалить). Ну и перепишите последнюю увиденную вершину.

Что-то типа такого:

int last_node = 0;
for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
   if (is_wall[i][j]) {
    last_node = -1;
  }  
  if (node_number[i][j] <- 0) continue;
  if (last_node > 0) {
    // добавить ребро между вершинами.
    AddEdge(last_node, node_number[i][j]);
  }
  last_node = node_number[i][j];
}

Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.

std::vector<int> DistributeExtraObjectsFairly(std::vector<int> objects, int extra_objects) {
    std::vector<int> permutation;
    permutation.reserve(objects.size()+1);
    permutation.resize(objects.size());
    std::iota(permutation.begin(), permutation.end(), 0);
    std::sort(permutation.begin(), permutation.end(),
        [&objects](const int &a, const int &b) {return objects[a] < objects[b];});
    int num_increased = 1;
    permutation.push_back(0);
    int step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased;
    while (extra_objects >= step && num_increased < objects.size()) {
        extra_objects -= step;
        ++num_increased;
        step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased; 
    }
    int final_value = objects[permutation[num_increased-1]] + extra_objects / num_increased;
    int num_bigger_values = extra_objects % num_increased;
    for (int i = 0; i < num_bigger_values; ++i) {
        objects[permutation[i]] = final_value + 1;
    }
    for (int i = num_bigger_values; i < num_increased; ++i) {
        objects[permutation[i]] = final_value;
    }
    return objects;
}

Идея: отсортировать числа и добавлять к минимальному, пока оно не станет равно следующему. Потом добавлять к двум мнимальным. Потом к трем и т.д. Вместо добавления к каждому числу индивидуально по одному объекту считаем, сколько надо объектов чтобы первые несколько первых стали равны следующему. Когда нашли, что дальше не приравнять - распределяем остаток среди затронутых элементов по-ровну, остатки кидая куда-то.

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

Edit: работает за O(n log n), где n - количество элементов в списке. Быстрее, я подозреваю, никак. Есть еще решение за O(n log M) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.

Знаки в условиях перепутаны.

Как обычно в вопросах про олимпиадные задачи, ответ тут - код не соптимизировать никак. Надо его переписать с нуля с более быстрым алгоритмом.

Смотрите на ограничания - n и m до 100000. Обычно такой порядок чисел означает, что вам нужно решение за O(n+m) или что-то вроде O(n+m log (n+m)). У вас же решение "в лоб" за O(nm), что никак не ускорить принципиально. Даже переписыванием на си со всякими хитростями вы ускорите его в 10, ну в 100 раз. А вам надо ускорить его в 10000 раз.

Могу дать подсказки:
Во-первых, если и там и там есть положительные элементы, то взяв максимальные в двух массивах вы точно получите элемент больше всех a и b. То же, если и там и там есть отрицательные элементы - надо взять два минимальных.

Остался случай - что если один массив целиком отрицателен, а второй - целиком положителен. Пусть a положителен, а b отрицателен. Что будет, если взять минимальные по модулю элементы и там и там? Посмотрите внимательно - вам дано, что ни одно из чисел не 0. Это поможет.

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

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

Просто воспользуйтесь алгоритмом ахо-корасика. У вас очень мало данных. Обработка их всех займет не более 100 мс на среднем компьютере в один поток.

Существующих готовых программ я не знаю, но реализацию алгоритма в библиотеках или на гитхабе я думаю вы найти сможете запросто.