P15364 [CTS 2026] Three-Color Garden (No testdata yet).

**This is a communication problem.**

Alice runs a beautiful garden with $n$ lounges for visitors to dine and rest, numbered from $1$ to $n$. Some flower corridors connect these lounges, allowing visitors to enjoy flowers and travel between lounges. Three different colors of flowers are planted in the corridors, and each corridor has exactly one of the three colors. To ensure order, for any two distinct lounges $u, v$ ($1 \le u < v \le n$), there is exactly one corridor connecting lounge $u$ and lounge $v$, and it can only be used in one direction. That is, the direction is either $u \to v$ or $v \to u$. When visiting the garden, tourists will choose a sequence of pairwise distinct lounges and travel around them in a cycle. Specifically, they choose $l$ ($l \ge 3$) lounges $a_1, \dots, a_l$, then travel in the order $a_1 \to a_2 \to \cdots \to a_l \to a_1$. Due to the direction constraints, there are few feasible tours. Define $a_1, \dots, a_l$ to be a **tour** if and only if $l \ge 3$, $a_1, \dots, a_l$ are pairwise distinct, and for all $1 \le i \le l$, the corridor between lounge $a_i$ and lounge $a_{(i \bmod l)+1}$ has direction $a_i \to a_{(i \bmod l)+1}$. Two tours $a_1, \dots, a_l$ and $b_1, \dots, b_{l'}$ are **essentially different** if and only if the corridors they traverse are different, or the cycle order is different; equivalently, $l \ne l'$ or for every $0 \le x < l$, there exists some $1 \le y \le l$ such that $a_y \ne b_{(y+x-1) \bmod l+1}$. For a tour, tourists will see flowers of different colors. If the corridors in the tour include all three colors, the tourists are satisfied; otherwise, they are dissatisfied. To ensure the experience, for each lounge, among the tours that pass through this lounge, **there are at most $k$ essentially different tours that make tourists dissatisfied**. Bob also wants to run a garden like Alice’s. He obtained Alice’s garden blueprint and built a garden with $n$ lounges as well. However, Alice lost the corridor design drawing. Bob wants the corridor layout and directions in his garden to be exactly the same as Alice’s, and also wants that for each lounge, among the tours passing through it, at most $k$ essentially different tours make tourists dissatisfied. **Note**: the flower colors planted in corridors do not have to be exactly the same; they only need to satisfy the condition above. To finish construction as soon as possible, Alice needs to send Bob as little information as possible so that Bob can build the corridors as required. Specifically, Alice may transmit a 01 string of length $l$. Bob must use this 01 string to build his garden’s corridors, i.e., determine the direction and flower color for the corridor between every pair of lounges. You need to help Alice send as little information as possible, and help Bob construct the corridors using this information. ### 【Implementation Details】 You do not need to, and should not, implement the `main` function. You must ensure your submitted program includes the header `garden.h`, i.e., add the following at the beginning: ```cpp #include "garden.h" ``` You need to implement the following three functions in your submitted source file: ```cpp int init(int n, int k); ``` - $n, k$ denote the number of lounges and the upper limit on the number of tours that make tourists dissatisfied, respectively. - This function must return a non-negative integer $l$, the length of the 01 string transmitted by Alice to Bob. You must ensure $0 \le l \le 1.5 \times 10^5$. - For each test point, this function is called exactly once by the interactive library when the program runs for the first time. ```cpp std::string send_message(int n, int k, std::vector e); ``` - $n, k$ denote the number of lounges and the upper limit on the number of tours that make tourists dissatisfied, respectively. - For $0 \le i \le n-2$, $0 \le j \le n-i-2$, $e_{i,j}$ represents the direction and flower color of the corridor connecting lounges $i+1$ and $i+j+2$ in Alice’s garden. Specifically, $e_{i,j}$ is a pair: - If the first element of $e_{i,j}$ is `true`, then the direction is $i+1 \to i+j+2$; otherwise it is $i+j+2 \to i+1$. - The second element is a non-negative integer in $\{0,1,2\}$, representing the flower color planted in that corridor. - This function must return a 01 string $s$ of length $l$, which is the 01 string transmitted by Alice to Bob. You must ensure that the length of $s$ equals the return value of `init`. - For each test point, this function is called exactly 10 times by the interactive library when the program runs for the first time, and the $n, k$ passed to it are the same as those passed to `init`. ```cpp std::vector build_flower_garden(int n, int k, std::string s); ``` - $n, k, s$ denote the number of lounges, the upper limit on the number of tours that make tourists dissatisfied, and the 01 string transmitted by Alice to Bob, respectively. - This function must return the direction and flower color of corridors in Bob’s garden, using the same representation as the variable $e$ passed to `send_message`. You must ensure: - The length of $e$ is $n-1$. - For $0 \le i \le n-2$, the length of $e_i$ is $n-i-1$. - For $0 \le i \le n-2$, $0 \le j \le n-i-2$, the second element of $e_{i,j}$ is a non-negative integer in $\{0,1,2\}$. - For each test point, this function is called exactly 10 times by the interactive library when the program runs for the second time. The $n, k$ passed to it are the same as those passed to `init` during the first run, and the $c$-th ($1 \le c \le 10$) string $s$ passed to it is the same as the return value of the $c$-th ($1 \le c \le 10$) call to `send_message` during the first run. - You must also ensure: - For $1 \le c \le 10$, $0 \le i \le n-2$, $0 \le j \le n-i-2$, the first element of $e_{i,j}$ passed to the $c$-th `send_message` call in the first run is the same as the first element of $e_{i,j}$ in the return value of the $c$-th `build_flower_garden` call in the second run. - The corridors built according to the return value satisfy: for each lounge, among the tours passing through this lounge, at most $k$ essentially different tours make tourists dissatisfied. **Note**: In all cases, the interactive library will run in no more than 0.2 seconds, uses fixed-size memory, and never exceeds 64 MiB. ### 【How to Test】 `stub.cpp` in the problem directory is a reference implementation of the interactive library. The interactive library used in the final evaluation is different from this reference implementation, so your solution must not depend on the library implementation. You can test using the following command in this problem directory: ```bash bash run.sh garden.cpp ``` #

- The script above will read data from **standard input** in the following format: - The first line contains three non-negative integers $t, n, k$, representing the number of testdata groups, the number of lounges, and the upper limit on the number of tours that make tourists dissatisfied. - Lines $i+1$ ($1 \le i \le n-1$) each contain $n-i$ non-negative integers. The $j$-th ($1 \le j \le n-i$) integer represents the direction of the corridor connecting lounges $i$ and $i+j$: if it is $1$, the direction is $i \to i+j$; otherwise it is $i+j \to i$. - Lines $i+n$ ($1 \le i \le n-1$) each contain $n-i$ non-negative integers. The $j$-th ($1 \le j \le n-i$) integer represents the flower color planted in the corridor connecting lounges $i$ and $i+j$. #

- The script above will output to **standard output** in the following format: - The first line contains a non-negative integer $l$, the length of the 01 string transmitted by Alice to Bob. - The second line contains a real number $p$ in $[0, 1]$, the score ratio for this test point. #

### 【Additional File Description】 In the additional files: 1. `stub.cpp` is the provided reference implementation of the interactive library. 2. `garden.h` is the header file; you do not need to care about its details. 3. `template_garden.cpp` is the provided sample code; you may refer to it and implement your own code. 4. `bigint.cpp` is a provided big integer template; you may refer to it and use it. 5. `bigint.pdf` is the usage guide for the big integer template. The additional files come from [QOJ](https://qoj.ac/contest/3343/problem/17205). ### 【Subtasks】 For all testdata, we have: - $t = 10$, $n = 300$, $0 \le k \le 2$. - All corridor directions are non-negative integers in $\{0,1\}$. - All corridor flower colors are non-negative integers in $\{0,1,2\}$. ::cute-table{tuack} | Subtask ID | Score | $k =$ | |:-:|:-:|:-:| | $1$ | $30$ | $0$ | | $2$ | $30$ | $1$ | | $3$ | $40$ | $2$ | ### 【Scoring】 **Note**: - You must not obtain internal information of the interactive library by illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. - The interactive library used for final evaluation is different from the sample interactive library. - This problem is also subject to the same limits as traditional problems. For example, a compilation error results in 0 points for the whole problem; runtime error, time limit exceeded, memory limit exceeded, etc. result in 0 points for the corresponding test point. You may only access variables you define and variables given by the interactive library; attempting to access other address spaces may cause compilation errors or runtime errors. - If the return value of `init`, `send_message`, or `build_flower_garden` is invalid, the corresponding test point scores 0. Based on the conditions above: - For each test point, let $B$ be the parameter of the subtask it belongs to, and let $l$ be the return value of `init`. The score ratio is given by the table below: ::cute-table{tuack} | Subtask ID | $B =$ | |:-:|:-:| | $1$ | $6\,200$ | | $2$ | $6\,800$ | | $3$ | $8\,000$ | ::cute-table{tuack} | $l \in$ | Score ratio | |:-:|:-:| | $[B + 5 \times 10^4, 1.5 \times 10^5]$ | $(5 + 15 \times (1.5 \times 10^5 - l) \div (10^5 - B))\%$ | | $[B + 10^4, B + 5 \times 10^4)$ | $(20 + (B + 5 \times 10^4 - l) \div 2000)\%$ | | $[B + 2 \times 10^3, B + 10^4)$ | $(40 + (B + 10^4 - l) \div 400)\%$ | | $(B, B + 2 \times 10^3)$ | $(60 + (B + 2 \times 10^3 - l) \div 50)\%$ | | $[0, B]$ | $100\%$ | - The score for each test point equals the score ratio multiplied by the score of the subtask that the test point belongs to. Translated by ChatGPT 5