Ця задача є інтерактивною.
Напередодні відкриття фестивалю десертів шеф-кухар ретельно вдосконалює фірмовий витвір своєї крамниці — «千层幻彩慕斯». Цей десерт складається з $n$ шматочків мусу з різними смаками, з послідовними номерами $0,1,\dots,n-1$.
Проте в метушні помічник випадково переплутав порядок шматочків мусу. Тепер вони стоять у ряд зліва направо, утворюючи невідому перестановку позицій $p=(p_0,p_1,\dots,p_{n-1})$, де $p_i$ — номер шматочка мусу на $i$-й позиції.
Щоб з'ясувати точне розташування кожного шматочка мусу, ви можете скористатися приладом для перевірки десертів. Щоразу, коли ви вибираєте три попарно різні позиції $x,y,z$, прилад повідомляє суму найменшого та найбільшого номерів цих трьох шматочків мусу:
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Дзвін, що сповістить про відкриття, ось-ось пролунає. Чи зможете ви за обмежену кількість перевірок точно відновити справжнє розташування кожного шматочка мусу?
Є перестановка довжини $n$, позначена $p$, елементами якої є рівно $0,1,\ldots,n-1$. Ви не знаєте вмісту $p$.
Ви можете вибрати три попарно різні індекси $x,y,z$, і бібліотека взаємодії поверне
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Ваше завдання — відновити всю перестановку. Обмеження на кількість запитів і спосіб обчислення балів залежно від кількості запитів наведено нижче.
Деталі реалізації
Учасникам не потрібно й не слід реалізовувати функцію main. Надісланий файл з кодом має містити:
#include "mousse.h"Ви маєте реалізувати дві такі функції:
void init(int c);
std::vector<int> mousse(int c, int n);- $c$ — номер підзадачі; $c=0$ позначає приклад. Кожен тест містить рівно один набір даних. Для цього тесту бібліотека взаємодії один раз викликає
init(c), а потім один раз —mousse(c,n). mousseмає повернути масив довжини $n$, у якому $i$-й елемент дорівнює $p_i$; індексація починається з $0$.
Учасники можуть зробити один запит, викликавши таку функцію:
int query(int x, int y, int z);Має виконуватися $0\le x,y,z < n$, а $x,y,z$ мають бути попарно різними. Функція повертає $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.
Тестування програми
У вкладеннях містяться mousse.h, локальна бібліотека взаємодії grader.cpp і приклад програми template_mousse.cpp. Збережіть свою програму у файлі mousse.cpp і виконайте в каталозі цієї задачі:
g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.inЛокальна бібліотека взаємодії зчитує приховану перестановку зі стандартного вводу; програма учасника не має самостійно зчитувати ці дані. Формат вхідних даних такий:
- Перший рядок містить два цілі числа $c,n$.
- Другий рядок містить $p_0,p_1,\ldots,p_{n-1}$.
Якщо відповідь правильна, бібліотека взаємодії виводить Correct! і Max queries used: Q, де $Q$ — кількість запитів у цьому тесті; якщо відповідь неправильна, вона виводить Wrong answer.. У разі некоректного запиту або перевищення обмеження на кількість запитів програма виводить повідомлення про помилку в стандартний потік помилок і завершується. Можна додати параметр -v, щоб побачити кількість запитів у цьому тесті.
Приклади
Вхідні дані 1
0 10
0 2 9 1 5 8 3 7 6 4Вихідні дані 1
Correct!
Max queries used: 15Пояснення
Наприклад, у разі виклику query(0,1,2) три відповідні значення дорівнюють $0,2,9$, тому повертається $0+9=9$. Програма-зразок використовує для цього набору даних $15$ запитів. Якщо ви застосуєте іншу стратегію, ця кількість може відрізнятися.
Обмеження
Для всіх тестових даних $n\in\{10,100,10^5\}$, а $p$ є перестановкою чисел $0\sim n-1$. Кожен тест містить рівно один набір даних.
| Номер підзадачі | Бали | $n =$ | $Q_{\max} = $ | Особлива властивість |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | Немає |
| $2$ | $5$ | $100$ | $10000$ | Немає |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | Немає |
Для прикладу $c=0$, $n=10$, а обмеження на кількість запитів дорівнює $1000$.
Оцінювання
Зверніть увагу:
- Бібліотека взаємодії не є адаптивною. Перестановку для кожного тесту визначено до виклику програми учасника, і вона не змінюється залежно від запитів.
- Учасники не мають отримувати приховану перестановку шляхом зчитування зі стандартного вводу або іншими недозволеними способами. Реалізація бібліотеки взаємодії, яку використовуватимуть під час остаточного оцінювання, може відрізнятися від локальної.
Якщо в певному тесті mousse повертає неправильну відповідь, параметри query некоректні або кількість запитів перевищує $Q_{\max}$ для цієї підзадачі, коефіцієнт оцінки за цей тест дорівнює $0$.
У підзадачах $1,2$ повну кількість балів за підзадачу можна отримати лише за правильні відповіді в усіх її тестах.
Для підзадач $3,4$, якщо коефіцієнт оцінки хоча б одного тесту дорівнює $0$, за всю підзадачу нараховується $0$ балів. Інакше нехай $Q$ — найбільша кількість запитів серед усіх тестів цієї підзадачі. Коефіцієнт оцінки $f(Q)$ визначається за наведеною таблицею:
| Кількість запитів $Q_i$ | Коефіцієнт оцінки $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
Якщо $Q\le 99970$, то $f(Q)=100\%$. Якщо $Q$ лежить між двома сусідніми рядками таблиці $(Q_i,f_i)$ та $(Q_{i+1},f_{i+1})$, то:
$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$
Оцінка за підзадачу $3$ дорівнює $30f(Q)$, а за підзадачу $4$ — $60f(Q)$. Остаточна оцінка округлюється до $3$ знаків після десяткової коми.
Обмеження часу: $10\ \mathrm{s}$.
Обмеження пам'яті: $512\ \mathrm{MiB}$.