Wataru

Проще "отсортировать" заданные координаты. Если 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 мс на среднем компьютере в один поток.

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

Может. Надо опять же через dfs рекурсией пройтись по дереву. Абсолютно тот же алгоритм что при кодировании, только вместо вывода бит - ввод. Вместо проверки вершины, ее создание.

Можно вместо рекурсии использовать стек вручную.

Edit: а вручную будет примерно так: Читаем бит. Если 0, то кладем в стек 0. Если 1, то текущий стек - код симола по следующим 8 битам и удаляем из стека все 1 сверху до первого нуля. Нуль меняем на 1.
Правда это даст не дерево а только коды символов. Чтобы получить дерево надо будет в стеке хранить указатели на вершины.

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

С обработкой контура с краем чуть-чуть сложнее. Тут можно добавить в граф фиктивную вершину, представляющую собой все края и соединить ее с фигурами, соединенными с краем. Дальше тем же самым алгоритмом надо проверить на наличие циклов. Есть только одно исключение - фигура в углу может сама иметь 2 ребра в край. Но тут можно добавить проверку в сам алгоритм - надо не останавливаться, если глубина стека равна 2, т.е. цикл получается только из края и одной фигуры.

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

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

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

Поскольку тут очень специфический граф - тут не надо никаких алгоритмов для графов. Это задача тупо на разбор случаев. Единственные возможные маршруты в этом графе - начать с какой-то вершины цикла и поехать вправо или влево, пока не доедете до черенка, и дальше по нему к выезду. Или можно начать на черенке и уехать. Очевидно, что первые два варианта - это надо начать с ближайшей к черенку елки в каждую сторону и поехать в ту же сторону дальше. Длина маршрута - количестов ребер минус рассотяние от елки до черенка в данную сторону. Третий путь можно начать на ближайшей к циклу елке на черенке и ехать на выход. Первые 2 варианта - если есть елки на цикле, третий вариант - если нет.

Вам надо только понять какие вершины в цикле, а какие на черенке. Тут можно обходом в глубину или ширину это найти. Или даже тупо циклом. В графе есть одна вершина степени 1 - она же выезд. От нее надо идти к соседним, пока не дойдете до единственной вершины степени 3. Пройденные так вершины будут черенком. Остальные - в цикле.

А дальше вам надо посчитать длины трех маршрутов и выбрать из них лучший.