% !TEX program = lualatex % (can also use "xelatex") 
\documentclass[12pt]{article}
\input{ejoi_structure.tex}

\usepackage[bulgarian]{babel}

\begin{document}

\renewcommand{\round}{Ден 2}
\renewcommand{\problemName}{Задача Пермутация}
\renewcommand{\lang}{Български}

\renewcommand{\tl}{$0.69$ sec.}
\renewcommand{\ml}{$256$ MB}
\problem{\problemName}

За някои от вас това може да бъде първата Ви encode-decode задача. Сигурни сме, че ще ви хареса \emoji{slightly-smiling-face}\\
Дадена е пермутация* на числата от 1 до N. Вие се стремите да сложите възможно най-много -1 в нея. Подробното описание е по-долу.\\\\
*Пермутация - каквато и да е редица съставена от N елемента, в която всяко число от 1 до N се среща точно един път.

\subsection{Детайли по имплементацията}
Задачата Ви е да имплементирате две функции:
\begin{lstlisting}
 std::vector<int> encode(std::vector<int> a);
\end{lstlisting}
Тя ще бъде извикана веднъж от журито и трябва да кодира пермутацията $a$. Вие я кодирате, като замествате числа от пермутацията с $-1$. След като сте преценили кои числа да заместите, връщате променената пермутация.
\begin{lstlisting}
 std::vector<int> decode(std::vector<int> a);
\end{lstlisting}
Тази функция ще бъде извикана веднъж от журито и трябва да декодира пермутацията, която сте кодирали в предишната функция (тоест като аргумент получавате Вашата пермутация със сложените от Вас -1). Вие трябва да я декодирате, като заменяте с -1 числoто, което е най-малкото неизползвано до момента. Целта е след тези промени възстановената пермутация да е същата като тази, която е подадена в \texttt{encode}.\\
Вашият код \textbf{не може} да съдържа глобална памет! Това означава, че двете функции не могат да комуникират и да съхраняват данни, които другата може да достъпи.

\subsection{Ограничения}
\begin{itemize}
\item $1 \leq N \leq 10^5$
\end{itemize}

\subsection{Оценяване}
Нека броя -1, които сте поставили при \texttt{encode} е $g$, а оптималния брой е $x$. Ако пермутацията, която връща \texttt{decode}, е различна от оригиналната, получавате 0 точки на съответния тест. В противен случай, точките се смятат по следната формула: \\
$points = min(1, \frac{g}{x})$ 

\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|}
\hline
\textbf{Подзадача} & \textbf{Точки} & \textbf{Допълнителни ограничения}\\
\hline
$1$ & $9$ & $a_i = i+1, 0 \leq i \leq N-1$ \\
\hline
$2$ & $11$ & $1 \leq N \leq 16$ или $17$ \\
\hline
$3$ & $13$ & В редицата с оптимално поставени -1, то се среща само веднъж. \\
\hline
$4$ & $67$ & Няма ограничения. \\
\hline
\hline
\end{tblr}
\end{table}
\FloatBarrier

\subsection{Пример}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|}
\hline
\textbf{Жури} & \textbf{Състезател}\\
\hline
$encode({4, 1, 2, 3, 5})$ & ${4, -1, 2, 3, 5}$\\
\hline
$decode({4, -1, 2, 3, 5})$ & ${4, 1, 2, 3, 5}$\\
\hline
\end{tblr}
\end{table}

\subsection{Примерен грейдър}
На първия ред се въвежда размера на редицата $N$, а на следващия ред-самата редица. Грейдърът извежда дали редицата съвпада при двете извиквания и колко -1 са сложени. 

\end{document}


