Лентюй, Если вам нужна скорость, то вопрос выбора языка перед вами не стоит вообще. Берете готовую библиотеку к языку в вашего проекта. Или выбираете язык по каким-то вашим критериям.
Сама же библиотека будет на С, вылизанная с ассемблерными вставками, и обернута в интерфейс для вашего языка.
AnT, Когда у вас глубина рекурсии достигает ~N в неоптимизированной реализации, то у вас сортировка, даже с вашей оптимизацией, будет работать за O(N^2). Если N такое большое, что O(N) памяти в стеке страшно завести, то вам в любом случае уже сильно поплохеет. Даже без оптимизации рекурсии.
А, раз человек не может разобраться с кодом, оптимизации можно для начала и исключить.
Потому что фигню сделали в quicksort(). Мало цикл закомментировать, надо всегда делать 2 рекурсивных вызова. А у вас один будет - в какой-то ветке if-else. Сравните с этим кодом.
Proshka17, Я каких-то косяков не вижу в решении. Дерево очень не эффективно реализовано, похоже. Может даже на за логарифм работает в определенных случаях, там как-то странно повороты делаются. Попробуйте написать сами дерево отрезков на сумму - это простая структура данных.
Далее, как я писал, заведите отрезок на n+m элементов и в последние m положите 1 - для каждого символа алфавита. И массив заведите второй, который будет для каждой позиции в отрезке говорить, какой символ там лежит. И еще один массив (what), который для каждого символа говорит, где он лежит в отрезке (where).
Потом, при шифровании, чтобы узнать, какой символ по счету, получаете его позицию в отрезке из вспомогательного массива и вызываете sum(0, where[one]-1). Потом перезаписываете where[one] в дереве отрезков на 0 и кладете 1 левее всех элементов (по счетчику, как у вас уже ключ уменьшается каждый раз на 1, только начинайте не с -1, а с n).
При дешифровке чуть сложнее. Надо будет как тут искать k-ую единицу. Потом вывести what[] от этой позиции и перенести единицу левее.
При переносе единицы не забудьте обновить what[] и where[].
так ключи и значения в массиве имеют однозначное соответствие. Что там искать?
Еще раз повторю. Дерево по неявному ключу. Эта структура позволяет за логарифм искать k-ый по порядку элемент, вставлять элемент в i-ое место и удалять элементы, не меняя относительный порядок остальных элементов. Все, что для этого нужно - хранить сколько вершин в поддереве в каждой вершине.
Вы храните перестановку в такой структуре. Еще есть обратный массив, который для каждого числа указывает, где оно в дереве хранится (указатель на вершину).
При шифровании надо узнать, какой "ключ" у заданного элемента. Это тоже реализуется проходом по дереву от вершины вверх. Потом перестановка элемента в начало - это log m + log m операций (удалить и вставить в начало).
При дешифровании надо узнать, какой элемент на k-ом месте и потом опять переставить элемент.
Второе решение, которое я сегодня дописал с деревом отрезков, возможно понятнее.
xmoonlight, Происходит n итераций шифрования/дешифрования, каждая итерация ищет, удаляет и добавляет элемент в балансированное дерево в котором m элементов.
У второго решения (с деревом отрезков) сложность O(n log(n+m)), потому что в отрезке n+m элементов.
Proshka17, Да, вызов не правильный же. Надо только один раз вызвать. Это раньше надо было перебирать, сколько карт им досталось. Теперь же достаточно просто зафиксировать разницу в 0. Т.е ответ - это просто один вызов.
Proshka17, Похоже фигня вот тут: DP(k - 1, t - v, i - (v > 0) - (v < a[k]), a, N)
В пересчете i флаги должы идти с разными знаками. Если первому игроку досталась карта - то +1, если второму, то -1 (ну, или наоборот). У вас же оба флага вычитаются.
условие на i<0, j<0 в первой проверке можно заменить на проверку, что разница по модулю не больше k. Ведь если у вас k типов карт роздано, то вы сможете получить от -k...k перевеса, отдав все или ни одной уникальнойкарты первому игроку
Второе условие - это база, когда роздано 0 типов карт. В этом случае перевеса нет и у первого игрока 0 карт. Т.е. условие t==0 && i==0. Тогда ответ 1. Иначе - 0.
Mercury13, для <= - да, но когда у вас проверка на неравнство нулю какого-то выражения - может на больших числах и получиться 0.00000000000003. Когда как численно - ответ 0.
Proshka17, Замените 2 последних параметра в ДП (50х50) на один -50..50. Вместо количества уникальных карт у каждого игрока считайте, на сколько у первого игрока уникальных больше.
Пересчет меняется просто. Если где-то вызывается от (..x,y), то надо вызываться от x-y. Для запоминания в массиве прибавляйте 50 к индексу.
Сама же библиотека будет на С, вылизанная с ассемблерными вставками, и обернута в интерфейс для вашего языка.