По неаккуратности ляпы можно допустить где угодно   И первоначальный вопрос как раз и состоял в:

И ляпы там были...


Вот именно, для малых N годится и вариант с бинарным поиском (номер 2 в первом сообщении этой ветки). Просто он не учитывает все условия задания - отсортированности обоих списков, а лишь отсортированность второго. И даже если отталкиваться от бинарного поиска, то отсортированность первого списка приводит к сужению границ поиска во втором, а понимание того, как сужаются границы, приводит к варианту volatile. Но просто вариант с бинарным поиском прокатить может.


В данном случае мы не ограничены во времени и отладке. И даже если такой тест пришлось бы проходить, то после его прохождения всё равно стоило бы устроить разбор полётов в том стиле, как шахматисты пересматривают свои (и не только) партии. Это и есть обучение.


Вот и я тупо взял решение от sQu1rr, и вуаля, тест пройден. И в чём смысл такого "программирования"?

Silent, в Вашем решении я не понял эту строчку:

Откуда там взялось волшебное число 10000?

feodorv, это по условию задачи


Silent, ваш вариант ялвяется логическим развитием варианта sQu1rr. Там действительно была некая ненадежность. При выходе значений из диапазона (-0x7FFF, 0x7FFF), программа сорершала сегфолт. Ваш вариант надежней в этом плане. Но скорость!
Это тот случай, о котором и говорил

умножив на перебор всех элементов, итоговая сложность вашего алгоритма N*logN
Зачем?  , Как я уже писал:

т.е. O(N). Причем, учтите, что это самый неблагоприятный случай. В реале, будет даже быстрее.
(Кстати, ваш алгоритм уступает не только по времени, но и по памяти.)

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

Добавлено @ 00:14
---
зы:я говорю о надежности по отношению к данным пользователя (foolproof).
защититься от сумасшедшего сопровождения (maintenance) увы, невозможно.  

Это сообщение отредактировал(а) volatile - 13.1.2012, 00:40

Туплю