Igor Borisov, Дело не в стиле. Дело в том, что там похоже меняли код случайным образом, пока на каком-то тесте не заработало. На других не работает, вот и спрашивают.
Alexandroppolus, можно и с О(sqrt(5000)) памяти. Сначала решетом найти для всех чисел до корня минимальный простой делитель. А потом искать gcd сливая списки простых. Если аккуратно подсчитать сколько там суммарно простых делителей среди всех чисел - будет линия.
Alexandroppolus, Я тоже сначала подумал про ответ за O(1). Даже какие-то формулы пытался выводить. Но там все не так просто, потому что надо, чтобы GCD(n,m) == 1, иначе тройки перебираются с повторами. Если и есть какая-то замкнутая формула, то там какой-нибудь ужас вроде дзетта-функции римана.
Даже не надо их генерировать. Достаточно перебрать n и m, найти k максимально возможное (поделив 5000 на c), прибавить к счетчику k. На максимум проверять надо 2km(m+n). У этого решения будет линейная сложность относительно ограничения на размер чисел.
asdsdsdafsdafdsaf, да, похоже на правду. Вот тут есть вообще код. Только его можно еще соптимизировать. Не надо копировать результат в начальный массив - лучше пусть функция принимает два вектора одинакового размера и по какому разряду надо сортировать. А дальше вызывайте ее перекладывая данные из одного вектора в другой и назад. Для этого удобно завести массив из двух векторов и класть из i%2 в (i+1)%2.
asdsdsdafsdafdsaf, неееет! Зачем там списки! Нужен лишь один вектор размера с сортируемый. За один проход в массиве на 256/65536 элементов считаете, сколько раз данная цифра в текущем разряде встречается. Потом за один проход пересчитываете, сколько чисел содержат меньшие данной цифру. Это будут индексы отрезков в результирующем массиве, куда надо поместить все числа с данной цифрой. Потом за второй проход все числа перемещает, увеличивая эти индексы.
Нет, этот изврат с генерированием псевдослучайной последовательности сделан, чтобы бороться с дико медленным вводом, который на разных языках и разными методами будет работать в разы медленнее или быстрее. Просто физически невозможно подобрать ограничения в задаче, которые бы надежно отсекали действительно быструю сортировку от не очень оптимальной, если 95% времени работы программы - ввод.
Метод генерации псевдослучайный как раз, чтобы шибко умные не придумали такую формулу.
asdsdsdafsdafdsaf, Хм... память под последовательность аккуратно один раз выделяете (capacity или resize у вектора)? Если все-равно не проходит, то, наверно, придется писать какой-нибудь radix sort. Естественно, сортировать надо не по десятичным цифрам, а, допустим, по байтам. Или по 4 бита в разряде.
if (a[5][j] > a[5][j - 1])Объясните мне, что этот код делает?