Wataru

Пока вижу проблему, которая 100% приведет к тайм-лимиту. Вы при изменении приоритета ищите по всей очереди. Если вам дадут 500000 добавлений в очередь, а потом 500000 уменьшений случаного элемента, то ждать вы завершения программы будете очень долго.

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

При изменении приоретета уже не надо никакого find, потому что позиция уже будет доступна в массиве.

При добавлении нового элемента не надо вызывать build_heap. достаточно только shift_up от нового элемента. У вас в программе отдельно этой функции нет, но она фактически реализована в decrease_key. Только нужно, опять же, проходится не по всей очереди, а только по отцам. В цикле надо делать не i--, а i = (i+1)/2-1.

И ошибка как раз в decrease_key, У вас цикл по i, а внутри все время используется k.

Пусть координаты x0,y0. Расстояние можно считать по этой формуле (вики).

Вам придется или скопировать код по ссылке и переписать на питоне, или использовать этот пакет.

Дальше, вам надо начиться отступать от заданной точки на север или восток на 1 метр. Это можно или медетировать над формулой выше а можно просто запустить бинарный поиск, который будет искать изменение широты или долготы. Пусть d - сколько вам надо отложить в метрах, R - радиус земли в метрах. Тогда ищите изменение на отрезке (0, 4*r*180/(2*Pi*R)). Пробуйте откладывать текущее значение по широте или долготе, считайте расстояние по формуле и, если оно больше d, заменяйте верхнюю границу отрезка на середину, иначе заменяйте нижнюю границу. Остановите бин.поиск, когда отрезок станет достаточно мелким (например <1e-10).

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

Сначала сгенерируйте точки на одной вертикале с начальной. Для этого повторно откладывайте 1м на север и юг от нее, пока расстояние до (x0,y0) не превысит ваш радиус. Бинпоиск достаточно запустить ровно один раз в самом начале и дальше именно это приращение откладывайте вверх и вниз.

Потом аналогичным образом откладывайте от каждой сгенеренной точки новые точки на запад и восток. Сначала для каждой точки бинпоиском найдите нужное приращение по долготе. Потом откладывайте его влево и вправо, пока не выйдите за радиус от (x0,y0).

В этой задаче все должно в long long помещаться. Никаких трюков не надо.

У вас ошибка вот тут:
long long div_up(int x, int y)

Типа параметров - int. Вы когда в эту функцию передаете long long сумму - происходит переполнение.

Просто измените типы на long long и должно пройти.

У вас какая-то странная схема в partition.

Представьте, что у вас массив из 2 элементов и первый - больше второго (a[0] = pivot > a[1]).

До цикла l = 0, h = 2, i = 0. Потом в первом while вы делаете i++. Потом сравниваете a[i] с pivot в первом while. a[1] < pivot по предположению, поэтому вы делаете i = 2. Все - вы уже вышли за границу массива.

Перепишите со стандартной схемой разбиения Хоара или Ломуто.

Или придется всякие условия i < j везде дописывать, но я не уверен.

Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.

Это называется топологическая сортировка. Реализуется обычно одним поиском в глубину. Есть статья на хабре.

Можно построить нужный вам порядок только для ациклических графов (без циклов).

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

Вроде все правильно. Какие ограничения? Может быть переполнение, ведь максимальный ответ n(n-1)/2. Для переполнения int достаточно 65536 чисел в массиве.

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

Варианты метрик:

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

Некоторые метрики имеют смысл только при фиксированном количестве кластеров, как первая.

Разные метрики дают разные кластеризации и все они в каком-то смысле хорошие. Что именно подходит вам в вашей задаче - можете судить только вы эмпирически.

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

Многие метрики, если они аддитивны как первая, можно считать динамическим программированием: f(i,k) - значение метрики если мы разбили первые i точек на k кластеров.

Для других, как для второй придется смешивать дихотомию по ответу и динамическое программирование (бинарный поиск по ответу, далее проверяем, а есть ли разбиение с такой или лучшей метрикой. Внутри динамика - минимально достижимое значение максимума между соседними точками в классе среди первых i при разбиении на k кластеров. При переборе последнего кластера нужно смотреть, чтобы расстояние между ним и соседними не превышало ответа динамики деленного на перебираемый коэффициент).

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

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

Это сложная задача - тут нет простого и быстрого алгоритма.

Можно свести ее к integer linear programming и решать какой-то из множества существующих библиотек/солверов. Если числа маленькие, то можно или полный перебор или какую-то динамику, типа решения задачи о рюкзаке сделать (тут надо будет набранные суммы во всех приборах взять в параметры).

Если нужно не обязательно оптимальное решение - а что-то не слишком ужасное, то можно делать жадность, как Adamos предложил.

При копировании назад из временного массива b в массив a у вас индексация с ошибкой. Хоть b индексируется с 0, вы обращаетесь к элементам начиная с s.

Вспомните алгоритм преобразования числа из 10-чной системы в t-ичную - надо делить на t с остатком, пока есть что делить. Остатки - цифры в t-ичной системе счисления (от младших к старшим).

Так, 323 в десятичной системе, если перевести в 16-ричную будет:
323 = 16*20+3. Остаток 3, результат 20.
20 = 16*1+4. Остаток 4, результат 1
1 = 16*0+1. Остаток 1. результат 0.

Отсюда получается, что искомое число в 16-ричной системе 143. Проверка 16*16*1+16*4+3 = 256+64+3=323

Итак, вам надо сделать то же самое, но не в 10-чиной системе, а в k-ичной (ведь переводим не из 10-чной а из k-ичной). Число записано в виде k-ичных цифр в массиве. Это, фактически, длинная арифметика с базой k.

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

Удобнее хранить цифры от младших к старшим в массиве. Т.е. элемент массива 0 - это единицы. Элемент 1 - это первая степень k. Еще стоит хранить номер последней ненулевой цифры. Смотрите реализацию по ссылке выше.

Вот пример из условия. Пусть k=666, t=10, число - {2, 179, 113} (в условии цифры от старших к младшим, но мы храним наоборот).

Делим на 10.

113/10 = 11 + остаток 3. Переносим 3 в младший разряд (умножив на 666), получаем 3*666+179=2177.
2177 / 10 = 217 + остаток 7. 7*666+2 = 4664.
4664 /10 = 466 + остаток 4. Дальше разрядов нет, значит 4 и есть остаток от деления {2, 179, 113} на 10. Результат деления - {466, 217, 11}

Последний остаток - 4 - это и есть младшая цифра в ответе (он в условии написан - 50241044). Надо продолжать делить результат пока он не окажется 0.

Повторим для {466, 217, 11}:
11/10 = 1 + остаток 1. 1*666+217 = 883
883/10 = 88 + остаток 3. 3*666+446 = 2444
2444/10 = 244 + остаток 4.
Опять, последний остаток - это остаток всего деления и следующая цифра в ответе (опять 4).
Результаты деления - {244, 88, 1}

И так далее, пока все число не станет 0 (все цифры в массиве 0).

Во-первых, для таких больших коэффициентов вы в long long не влезаете, если в лоб считать.

Можно проверить в 2 этапа. Подсчитать A=a*x+b, B=c*x+d. Потом проверить что A*x*x = -B. Но тут нужно заранее отсечь случаи, когда abs(A) > abs(B)/(x*x). Тогда переполнений не будет.

Во-вторых, как же сложно у вас разбор случаев идет. Я не могу разобраться, что там происходит. Там наверняка опечатка, но я даже читать не хочу. Перепишите, пожалуйста. Вам надо найти самый старший ненулевой коэффициент и перебирать его делители. Плюс добавить корень 0, если этот коэффициент не d. Это делается сильно проще так:

if (d != 0) {
  n = d;
} else {
  s.push_back(0);
  if (c != 0) {
    n = c;
  } else if (b != 0) {
   n = b;
  } else {
   n = a;
  }
}
if (n == 0) {cout << "-1"; return}

Самое простое решение для понимания - полный перебор. Тупо 3 цикла - сколько монет с номиналом 2 взяли, сколько монет с номиналом 3 и сколько монет с номиналом 5. Каждый цикл от 0 до <Сколько осталось набрать> / номинал. Потом проверяем, что сумма сошлась. Более того, можно последний цикл пропустить и просто проверить, что оставшееся можно набрать пятаками.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}

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

Самое быстрое решение - динамическое программирование.

F(n,k) - можно ли набрать число n первыми k типами монет.

F(0.0) = 1
F(*, 0) = 0
F(n,k) = Sum(i = 0..have[k]) F(n-i*value[k], k-1)

Фактически, это тот же рекурсивный перебор, только с мемоизацией. Можно переписать это двумя циклами и соптимизировать по памяти до O(n).

Проблема в выводе. Вы нулевые цифры вообще не выводите:

for(size_t i=0; i<SIZE; i++) {
  if (n[i]!=0) {
    cout << n[i];
  }
}

А нужно пропускать только ведущие нули. Самый простой способ исправить - завести bool printed:

bool printed = false;
for(size_t i=0; i<SIZE; i++) {
  if (printed || n[i]!=0) {
    cout << n[i];
    printed = true;
  }
}

Ну, еще может быть стоит увеличить размер длинных чисел. Не факт, что 135 цифр хватит. Введите тест n=300, k=300, и проверьте что выводится один и тот же ответ при текущем и увеличенном SIZE.