Есть решение, но оно на плохих тестах, если не повезет, не влезет в лимит.
Чтобы вам повезло, можно "перемешать" входные данные случайным образом. Заведите случайную перестановку. Далее внизу я про нее как бы забуду, но когда я говорю спросить про элементы i и j вы должны справшивать про p[i] и p[j]. Как только вы найдете, что 0 в p[k] - про эту случайную перестановку можно забыть и далее использовать элемент p[k] для востановления перестановки.
Спросите про элементы 0 и 1. Запомните a[0] | a[1].
Вот у вас есть 2 элемента каких-то, вы знаете их позиции и a[i]|a[j]. Мы будет добавлять к ним элементы 2..n-1 по одному, все время выбрасывая один или несколько, в которых нуля точно нет.
Вот есть у вас элеметы x, y и вы знаете a=x|y. возьмем новый элемент z и спросим b=y|z.
Мог ли 0 быть в x? тогда бы a = x|y=0|y = y. Т.е. предыдущее значение a должно вкладываться в новое b как множество единиц. Аналогичный критерий для возможности z быть нулем - b вкладывается в a.
Eсть 4 взаимоисключающих варианта, как множества бит a и b соотносятся:
1) a целиком вкладывается в b, или a|b == b, a != b, например 5 вкладывается в 7.
2) b целиком вкладывается в a, или a|b == a, a != b
3) a == b
4) ничего из выше перечисленного, например, 3 и 6.
Мы уже становили, что x может быть 0 только в случаях 1) и 3). z может быть нулем только в случаях 2) и 3).
В каких случаях может быть нулем y? только в 1), 2) и 4)
Теперь алгоритм, если выпал случай 1), то мы выбрасываем z. При этом значение текущего OR уменьшилось как множество.
Если выпал случай 2), то мы выбрасываем x. При этом значение текущего OR уменьшилось как множество.
Если выпал вариант 3), то мы выбрасываем y и нам придется спросить x|z, ведь нам надо знать OR оставшихся элеметов. Это плохо тем, что мы спросили 2 раза, рассморев один новый элемент. В неудачном случае мы бы задали 2n вопросов только ища 0 и у нас не осталось бы квоты на восстановление самой перестановки.
Но тут есть 2 подварианта. 3а) Если значение x|z стало меньше, как множество, то ок. 3б) Но оно еще могло бы остаться таким же, т.е. x|y=y|z=x|z. Но в этом случае, по аналогичным рассуждениям нуля не может быть нигде среди этих трех элементов! А значит мы можем выкинуть и их все, избавившись от двух элементов за два вопроса.
Если выпал вариант 4), то мы выбрасываем x или z.
Таким образом задав от n до 2n (в самом неудачном случае) мы получаем в конце 2 элемента в одном из которых точно 0, а второй - a.
Чтобы восстановить кто из двух оставшихся элементов кто: по ходу отсеивания, задавая любой вопрос запоминайте для какой пары чисел вы видели нулевой бит в каждом разряде. (Т.е. спросили про i|j получили ответ 5. Тут второй бит 0, значит запомнили, что i|j дает 0 в бите 2. И поддерживайте массив для всех разрядов).
Если вам хоть сколько-нибудь повезет. вы наберете достаточно таких примеров.
Теперь пройдитесь по всем примерам, что вы ранее видели и выберите тот, который имел 0 в разряде, где у a стоит 1. пусть это были элементы i и j. Теперь спросите x|i. Если и там этот разряд 0, то x=0, иначе у=0.
Тут почти нарисовался строго убывающий инвариант - размер множетсва бит в OR для текущих кандидатов, но пункт 3б) его ломает, ведь мы получаем 2 новых элемента и множество может стать любым. Но случайный порядок вопросов должен сделать этот вариант маловаероятным. У вас запас примерно 150 впоросов на максимальном тесте. Возможно тут можно придумать какую-то строгую схему, где какой-то инвариант строго убывает на лишних вопросах и может убывать не более 100 раз.