P15845 [Bulgarian NOI 2024] GCD5.0

When submitting this problem on Luogu, please choose the language standard >= C++17. You do not need to include `#include "gcd5.h"`. Instead, put ```cpp long long query(int x); void answer(long long a, long long b); void solve(int n); ``` at the beginning of your program.

This problem has nothing to do with GCD :) Niki has already chosen $N$ **hidden lines** (or linear functions), and you need to find them. Formally, the $i$-th line is defined by a pair of coefficients $(a_i, b_i)$, and represents the linear function $f_i(x) = a_i \cdot x + b_i$. Niki does not like fractions, so all coefficients are **integers**. To find these hidden lines, you can ask queries of the form: “at a given integer $x$, which line attains the maximum value”. As you already know, Niki hates decimals, so you can only ask this for **integer** values $x$. Formally, the answer to such a query is $\max_{1 \le i \le N} f_i(x)$. It is guaranteed that a solution exists. Besides the conditions above, it is also guaranteed that each line becomes the maximum for at least **$3$ integer values** $x$ within the interval $[-10^9; 10^9]$; in other words, for every line $i$, there exist at least 3 values $x \in [-10^9; 10^9]$ such that for all $j \ne i$, $f_i(x) \ge f_j(x)$. In addition, **no two lines have the same slope $a_i$**. Write a program that finds all hidden lines using as few queries as possible. ### Interaction Format This is an interactive problem. You only need to implement a `solve` function of the following type: ```cpp void solve(int n); ``` This function will be called exactly once, with the parameter equal to the number of lines. Your implementation may use the following two helper functions: ```cpp long long query(int x); void answer(long long a, long long b); ``` By calling `query(x)`, you can obtain the maximum function value among all lines at the given $x$. The score you get for each test depends on how many times you call this function. **You may only call this function for $x \in [-10^9; 10^9]$.** The `answer` function must be called exactly $n$ times—once for each line you find. The order of calls does not matter. Your code **must not include a `main` function**, but it may include other helper functions, classes, variables, etc. Your code must include the header file `gcd5.h`. ```cpp #include "gcd5.h" ``` For convenient local testing, we provide a local grader `Lgrader.cpp` and a copy of the header file `gcd5.h`. You need to compile your code together with the local grader for testing. You can put them in the same folder and use the following command: ```bash g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gcd5.cpp Lgrader.cpp -o gcd5.exe ```

N/A

N/A

### Example Let $N = 2$, and the hidden lines are $(1, -5)$ and $(-1, 5)$. One possible interaction process is as follows: | Contestant | Grader | |:----:|:----:| | | `solve(2)` | | `query(1)` | 4 | | `query(5)` | 0 | | `query(6)` | 1 | | `answer(-1, 5)` | | | `answer(1, -5)` | | ### Subtasks | Subtask | Score | $N \le$ | |:------:|:----:|:-----------:| | $1$ | $18$ | $100$ | | $2$ | $33$ | $5000$ | | $3$ | $49$ | $10^5$ | The score of a subtask equals the minimum score among all its subtest points. ### Scoring For each test point, you will receive a result computed as follows: 1. If you make an invalid query, or fail to correctly identify all hidden lines, the score is 0. 2. Let $Q$ be the total number of queries you made. 3. If $Q > 5 \times 10^6$, the score is 0. 4. Otherwise, the score for that test point is: $$ \min\left\{ 0.25 + 0.75 \times \left( \frac{4N}{Q} \right)^2,\ 1.0 \right\} $$ ### Constraints - $1 \le N \le 10^5$. - $|a_i| \le 10^9$, and each $a_i$ is an integer. - $|b_i| \le 10^{18}$, and each $b_i$ is an integer. Translated by ChatGPT 5