Background

When submitting this problem on Luogu, please choose the language standard >= C++17. You do not need to include #include "gcd5.h". Instead, put

long long query(int x);

void answer(long long a, long long b);

void solve(int n);

at the beginning of your program.

Problem Description

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:

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:

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.

#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:

g++ -O2 -std=c++17 -Wl,--stack,1073741824 -Wall gcd5.cpp Lgrader.cpp -o gcd5.exe

Hint

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