P10832 [COTS 2023] Passing Mapa

Translated from [Izborne Pripreme 2023 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2023/) D2T1. $\texttt{1s,0.5G}$. Happy birthday to NaCly_Fish! (2024.7.28) ~~**Due to limitations of the Luogu judging system (this problem requires run-twice), this problem cannot be judged.**~~

You are given $N$ pairs of positive integers in $[1,10^9]$. Similar to $\texttt{std::map}$ in C++, you can treat the first number of each pair as a "key" and the second number as a "value". It is guaranteed that all keys are distinct, and you can query the value by its key. You want to send these $N$ pairs of positive integers, but due to bandwidth limits, you can only compress them into a $\texttt{01}$ string for transmission. Write a program to compress these $N$ pairs of positive integers into a $\texttt{01}$ string; or, given the $\texttt{01}$ string you constructed, answer $Q$ queries: for each given key, you must output the corresponding value.

The first line contains a positive integer $T\in \{1,2\}$, indicating the data type. If $T=1$, it is an encoding task; otherwise, it is a decoding task. - When $T=1$: The second line contains an integer $N$, the number of pairs. The next $N$ lines each contain two positive integers $x_i,y_i$, representing the key and the corresponding value. - When $T=2$: The second line contains three positive integers $N,Q,K$, representing the number of pairs, the number of queries, and the length of the $\texttt{01}$ string. The third line contains a $\texttt{01}$ string of length $K$. The next $Q$ lines each contain one positive integer $x_i$, the queried key.

- When $T=1$: The first line contains a positive integer $K$, the length of the $\texttt{01}$ string you constructed. The second line contains the $\texttt{01}$ string you constructed. - When $T=2$: Output $Q$ lines, each containing one positive integer, the corresponding value.

#### Constraints For $100\%$ of the testdata, it is guaranteed that: - $T\in \{1,2\}$. - $1\le N,Q\le 100$, $1\le K\le 6\, 000$. - $1\le x_i,y_i\le 10^9$. - All $x_i$ are pairwise distinct. #### Scoring If your output format is incorrect or you do not answer the queries correctly, you get $0$ points. Otherwise, let $K$ be the length of the $\texttt{01}$ string you output. Your score is determined by the following table: | $K$ | Score | |:-----:|:------:| | $K\gt 6\, 000$ | $0$ | | $3\, 000\le K\le 6\, 000$ | $\displaystyle 100- \frac{K-3\, 000}{30}$ | | $K\le 3\, 000$ | $100$ | Translated by ChatGPT 5