Это интерактивная задача.
Накануне открытия фестиваля десертов шеф-повар тщательно доводит до совершенства фирменное творение своей кондитерской — «千层幻彩慕斯». Этот десерт состоит из $n$ кусочков мусса с разными вкусами, пронумерованных последовательно от $0$ до $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). $$
Звонок, возвещающий открытие, вот-вот прозвучит. Сможете ли вы за ограниченное число проверок точно восстановить положение каждого кусочка мусса?
Дана перестановка $p$ длины $n$, элементы которой — в точности $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$ до $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}$.