P15845 [Bulgarian NOI 2024] GCD5.0
题目背景
在洛谷上提交此题，请选择 >=C++17 的语言标准，不需要引入 `#include "gcd5.h"`，而是将
```cpp
long long query(int x);
void answer(long long a, long long b);
void solve(int n);
```
放在程序开头。
题目描述
题目与 GCD 毫无关系 :)
妮基已经想好了 $N$ 条**隐藏的直线**（或线性函数），而你需要找出它们。形式化地，第 $i$ 条直线由一对系数 $(a_i, b_i)$ 定义，并表示线性函数 $f_i(x) = a_i \cdot x + b_i$。
妮基不喜欢分数，因此所有系数都是**整数**。
为了找到这些隐藏的直线，你可以提出关于“在给定整数 $x$ 处，哪条直线取得最大值”的查询。正如你已了解到的，妮基讨厌小数，所以你只能对**整数值** $x$ 提出这个问题。形式上，对该问题的回答是：$\max_{1 \le i \le N} f_i(x)$。
题目保证有解。除了上述条件外，还保证每条直线在区间 $[-10^9; 10^9]$ 内至少有 **$3$ 个整数值** $x$ 使其成为最大值；换句话说，对于每条直线 $i$，存在至少 3 个值 $x \in [-10^9; 10^9]$，使得对所有 $j \ne i$，都有 $f_i(x) \ge f_j(x)$。此外，**没有两条直线具有相同的斜率 $a_i$**。
请编写一个程序，使用尽可能少的查询次数，找出所有隐藏的直线！
### 交互格式
本题为交互式题目，你只需实现一个类型为以下的 `solve` 函数：
```cpp
void solve(int n);
```
该函数将被精确调用一次，参数等于直线的数量。你的实现可以使用以下两个辅助函数：
```cpp
long long query(int x);
void answer(long long a, long long b);
```
通过调用 `query(x)`，你可以获取在给定 $x$ 处所有直线中的最大函数值；你在每个测试点能获得的分数取决于你调用该函数的次数。**你只能对 $x \in [-10^9; 10^9]$ 范围内的值调用此函数。**
`answer` 函数必须被精确调用 $n$ 次——每发现一条直线就调用一次。调用顺序无关紧要。
你的代码中**不应包含 `main` 函数**，但可以包含其他辅助函数、类、变量等。你的代码必须包含头文件 `gcd5.h`。
```cpp
#include "gcd5.h"
```
为便于本地测试，我们提供了本地评测器 `Lgrader.cpp` 以及头文件 `gcd5.h` 的副本。你需要将你的代码与本地评测器一起编译以进行测试。你可以将它们放在同一文件夹中，并使用以下命令：
```bash
g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gcd5.cpp Lgrader.cpp -o gcd5.exe
```
输入格式
无
输出格式
无
说明/提示
### 示例
设 $N = 2$，隐藏的直线为 $(1, -5)$ 和 $(-1, 5)$。一次可能的交互过程如下：
| 选手 | 评测机 |
|:----:|:----:|
| | `solve(2)` |
| `query(1)` | 4 |
| `query(5)` | 0 |
| `query(6)` | 1 |
| `answer(-1, 5)` | |
| `answer(1, -5)` | |
### 子任务
| 子任务 | 分数 | $N \le$ |
|:------:|:----:|:-----------:|
| $1$ | $18$ | $100$ |
| $2$ | $33$ | $5000$ |
| $3$ | $49$ | $10^5$ |
某子任务的得分等于其所有子测试点中得分的最小值。
### 评分方式
对于每个测试点，你将获得一个按以下方式计算的结果：
1. 如果你提出无效查询，或未能正确识别所有隐藏的直线，则得分为 0。
2. 设 $Q$ 为你提出的总查询次数。
3. 如果 $Q > 5 \times 10^6$，则得分为 0。
4. 否则，该测试点的得分为：
$$
\min\left\{ 0.25 + 0.75 \times \left( \frac{4N}{Q} \right)^2,\ 1.0 \right\}
$$
### 限制条件
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$，且每个 $a_i$ 是整数。
- $|b_i| \le 10^{18}$，且每个 $b_i$ 是整数。