Editorial

Будемо нумерувати біти регістру справа наліво починаючи з $0$. Виходить, що перший справа біт регістру "— біт під номером $0$.

Підзадача 1. Підзадача розв'язується у $3$ запити: $setNot(2,1)$, $shiftLeft(2,63)$, $shiftRight(2,63)$. Можна здогадатися, що $0$-ий біт регістра відповідає за парність числа. Якщо цей біт рівний нулю, то число парне, якщо рівний одиниці "— непарне. Після операції $setNot(2,1)$ у регістрі під номером $2$ буде навпаки: якщо $0$-ий біт рівний $1$, то число у регістрі $1$ було парним, а інакше "— непарним. Після зсунення другого регістру спочатку на $63$ позиції вліво, а потім на $63$ вправо залишиться лише $0$-ий біт, усі інші стануть рівні $0$. Отже, у другому числі буде записано число $1$, якщо перше було парним, і $0$, якщо перше число було непарним.

Підзадача 2. Для розв'язання цієї підзадачі потрібно використати таку формулу: $a+b=(axorb)+(aandb)\cdot 2$ . Її коректність легко довести, розглядаючи числа $a$, $b$ та їх суму у двійковій системі числення: якщо конкретний біт під номером $x$ рівний $1$ і в $a$, і в $b$, то до суми $a+b$ додається $2^{x+1}$, а якщо лише в числі $a$ або лише в числі $b$, то до суми додається $2^x$. Операцію множення на двійку можна замінити зсувом уліво на одну позицію. 64 рази зробимо такі операції: $setValue(3,2)$, $setXor(2,1,2)$, $setAnd(1,1,3)$, $shiftLeft(1,1)$. За допомогою формули ми розуміємо, що після будь-якої кількості таких операцій сума перших двох чисел буде рівна сумі двох початкових чисел. Також за $64$ операції число у регістрі $1$ гарантовано перетвориться на нуль, адже ми $64$ рази зсували його вліво. З цього маємо, що число, яке стоятиме на позиції $2$, і буде відповіддю. Тому в кінці робимо операцію setValue(3, 2);

Підзадача 3. Розв'язавши підзадачу $2$, ми навчилися знаходити суму будь-яких двох чисел. В окремому регістрі ми будемо зберігати відповідь "— кількість одиниць. Будемо називати виділенням біта створення регістру, у якому залишився лише один цей біт, а всі інші перетворилися на $0$. Для виділення біта під номером $i$ потрібно зсунути регістр на $63-i$ позиції вліво, а потім на $63$ позицій вправо. У такий спосіб ми розглянемо окремо кожен з $64$ бітів і просумуємо його з регістром-відповіддю. Ми вміємо знаходити суму двох чисел за $64$ ітерації, а цього було не достатньо.

Потрібно помітити, що відповідь не може перевищувати $64$, а отже, зберігається в перших $7$ бітах. Тому при додаванні регістрів можна робити не $64$ ітерації, а всього $7$. Для меншої кількості операцій ми повинні помітити, що після додавання першого біта до відповіді використовується максимум $1$ біт (можна робити всього $1$ ітерацію замість $64$), після додавання двох бітів використовується $2$ біти (можна робити $2$ ітерації), при додаванні $4$ бітів використовується $3$ біти (можна робити $3$ ітерації) і так далі. Цих прискорень достатньо для отримання повного балу.

Підзадача 4. Для початку зробимо такі операції: $setXor(3,1,2)$, $setAnd(1,1,3)$, $setAnd(2,2,3)$. Після таких операцій задача зовсім не зміниться (більше число залишиться більшим), проте числа не будуть мати позицій з однаковими бітами. Після цього ми для обох чисел на позиціях $1$ та $2$ робимо таке: робимо операцію Or між числом і його копією, зсунутою на $1$ позицію вправо, потім Or між новим числом і копією нового, зсунутого на $2$ позиції вправо, потім зсунутого на $4$ позиції вправо, потім на $8$ і так до $32$. Після цього задача знову не зміниться, тому що для кожного числа не виникне одиничного біта, старшого за той, що був найстаршим до операцій. Якщо після цього зробити $xor$ $1$-ого і $2$-ого чисел, менше число перетвориться на $0$, а більше матиме принаймні один біт, рівний 1. Тепер якщо проробити такі ж операції знову, але зсувати вліво, то менше число залишиться $0$-ем, а більше число матиме $63$-ий біт, рівний $1$. Тому якщо після цього зсунути числа на $63$ позицій вправо, більше число перетвориться на $1$, а менше на $0$.

Підзадача 5. Будемо зберігати відповідь в окремому регістрі. Зробимо $64$ ітерації. Спочатку зробимо операцію or поточної відповіді і її ж зсунутої на $1$ позицію вліво. Також на ітерації $i$ ми відокремимо біт із початкового числа й поставимо його найстаршим бітом зсунувши, на $63-i$ позицій вліво. Для кожного біта $i$ зробимо $64$ рази такі операції: результат операції and регістру біта $i$ та поточної відповіді прооримо (зробимо операцію $or$) з певним іншим регістром, у якому будемо зберігати відповідь для ітерації $i+1$, а сам біт $i$ зсунемо на одну позицію вправо. Після цих $64$ операцій потрібно проорити регістр із відповіддю на $i$-ій ітерації та на $i+1$-ій. Якщо біт $i$ був одиницею, то на ітерації $i+1$ відповідь буде мати ще $1$ одиницю, приписану зліва від уже записаних. Після $64$ ітерацій усі одиничні біти числа зсунуться вправо (те, що і потрібно в задачі, якщо переформулювати).

Підзадача 6. Розв'язавши підзадачу $4$, ми навчилися перетворювати максимум з двох чисел на $1$, а мінімум на $0$. Також ми вміємо перетворювати число $1$ у число $2^{64}-1$ за допомогою зсувів на $1$, $2$, $4$, $\dots$, $32$ позиції вліво. Якщо проендити (зробити операцію and) числа $0$ та $2^{64}-1$ і відповідні початкові числа, тоді максимальне число залишиться тим самим, а мінімальне перетвориться на $0$. Прооривши їх (зробивши операцію or), отримаємо максимум. Зробивши аналогічні операції, але інвертувавши (операція setNot) $0$ та $2^{64}-1$, ми знайдемо мінімум. Тепер ми можемо отримати мінімум і максимум серед двох чисел. Тому ми можемо написати сортування бульбашкою, адже для двох чисел можемо в перше число записати мінімум, а в друге число записати максимум, а саме це і потрібно для алгоритму сортування.