Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, неееет! Зачем там списки! Нужен лишь один вектор размера с сортируемый. За один проход в массиве на 256/65536 элементов считаете, сколько раз данная цифра в текущем разряде встречается. Потом за один проход пересчитываете, сколько чисел содержат меньшие данной цифру. Это будут индексы отрезков в результирующем массиве, куда надо поместить все числа с данной цифрой. Потом за второй проход все числа перемещает, увеличивая эти индексы.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, кстати, вы же нормально radix sort сделали - без рекурсии, начиная с младших разрядов?

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, можно попробовать по 2 байта. Тогда будет в 2 раза меньше проходов, но они сами медленнее из-за большего разброса в памяти.

Иначе остаются микрооптимизации: не делить нацело, а использовать битовые маски, не выделять лишнюю память.

Как найти сумму чисел на нечетных позициях после сортировки массива?

Нет, этот изврат с генерированием псевдослучайной последовательности сделан, чтобы бороться с дико медленным вводом, который на разных языках и разными методами будет работать в разы медленнее или быстрее. Просто физически невозможно подобрать ограничения в задаче, которые бы надежно отсекали действительно быструю сортировку от не очень оптимальной, если 95% времени работы программы - ввод.

Метод генерации псевдослучайный как раз, чтобы шибко умные не придумали такую формулу.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, А если бы L было поменьше, то можно было бы делать сортировку подсчетом.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, Хм... память под последовательность аккуратно один раз выделяете (capacity или resize у вектора)? Если все-равно не проходит, то, наверно, придется писать какой-нибудь radix sort. Естественно, сортировать надо не по десятичным цифрам, а, допустим, по байтам. Или по 4 бита в разряде.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, Точно такие ограничения? L до 2^32?

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, Ну, делать merge по мере генерации - это почти гарантированно O(N^2). Там надо очень сильно извратиться, чтобы логарифм в итоге получить.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, Посмотрел ограничения - удивился. Что, встроенная в язык сортировка (например std::sort в C++) не проходит? Ваша реализация merge sort наверняка далеко не оптимальна.

Как найти сумму чисел на нечетных позициях после сортировки массива?

asdsdsdafsdafdsaf, Какие ограничения на время, N, L?

Как в vector на си вставлять элемент на конкретное место?

pshevnin, Ну тогда, да, ваш подход будет работать. Просто увеличивайте массив, чтобы все индексы существовали. Не забудьте через memset затереть новую область нулями.

Как в vector на си вставлять элемент на конкретное место?

pshevnin, Нет у вас не массив тогда, а словарь. Вам надо реализовывать какое-то бинарное самобалансирующееся дерево, или хеш-таблицу.

Если хотите делать массивом, то тогда вам не надо ничего сдвигать memove. Я то думал что вы вставляете элементы по порядковому номеру, а не абсолютному индексу. В вашем случае вам придется увеличивать массив так, чтобы capacity было больше вставляемого id. Может придется в цикле увеличивать массив в VECTOR_SIZE_MULT раз, или высчитывать размер массива в зависимости от id.

Но тут может быть большая проблема с тем, что если id расположенны не плотно, то у вас будет очень большое потребление памяти (вот введу я вам id=2000000000 - вам придется выделить пару десятков гигабайт памяти). Да и работать это будет на порядки медленнее словаря.

Как в vector на си вставлять элемент на конкретное место?

pshevnin, Т.е. у вас массив на 10 элементов и вам надо вставить на индекс 100?

Последнюю строку массива мне выводит очень много раз, в чем проблема?

Паша Максименко, Не могу сказать, потому что не знаю, что этот код должен делать.

Последнюю строку массива мне выводит очень много раз, в чем проблема?

Введи код в редакторе. Выдели его весь и нажми на кнопку </>, прокрути до C++ и ткни туда.
Вокруг кода появятся теги code.

Выглядить это будет вроде:

#include <iostream>

int main() {
  std::cout << "Hello world";
  return 0;
}

Никакие части кода не исчезнут.

Как сделать проверку числа на повторность в массиве?

Retr0Hacker,

Большое спасибо также за мотивацию! Я докажу вам и себе лично что шарю за программирование и станю отличным спецом.

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

А можете ли вы посоветовать какие-нибудь материалы по Си

Да что угодно. Введите в гугл "Уроки Cи" и берите первую попавшуюся ссылку.

Как сделать проверку числа на повторность в массиве?

Retr0Hacker, Нет, решать за вас ваше задание я не буду. Если после прочтения моего ответа вам все еще не понятно (что, цикл for проходящий по массиву написать не можете?), то вам дальше никак в программировании не получится. Или бросайте ваш курс, или нанимайте репетитора. В крайнем случае, идите на какой-нибудь freelance.habr.com и вам там за деньги ваше задание решат.

Деление строки на 2 части и преобразование в int?

дмитрий шевченко, для считывания слеша там как раз идет считывание символа с.
Можно еще кучу проверок добавить через file.peak - что начинается число, что следующий за ним символ - слеш, что число прочиталось. Но если вы уверены в формате, то вам не надо даже читать строку и разбивать ее руками. ifstream сам прочитает число до слеша.

Деление строки на 2 части и преобразование в int?

Выведите text - наверняка у вас в файле есть пустые строки и вот в такой строке / не находится.

Вы можете читать вот это средствами самого file (это же ifstream, да?):

int day, month;
char c;
cin >> day >> c >> month;

Почему разрывает соединение, при смене типа?

Илья, приведите код с классом.