34278번 - Hack! 서브태스크점수다국어언어 제한함수 구현

문제

It has been an hour into a Codeforces contest, when you notice that another contestant in your room has solved a problem using an unordered_set. Time to hack!

You know that unordered_set uses a hash table with $n$ buckets, which are numbered from 0ドル$ to $n − 1$. Unfortunately, you do not know the value of $n$ and wish to recover it.

When you insert an integer $x$ into the hash table, it is inserted to the ($x \bmod n$)-th bucket. If there are $b$ elements in this bucket prior to the insertion, this will cause $b$ hash collisions to occur.

By giving $k$ distinct integers $x[0],x[1], \dots ,x[k − 1]$ to the interactor, you can find out the total number of hash collisions that had occurred while creating an unordered_set containing the numbers. However, feeding this interactor $k$ integers in one query will incur a cost of $k$.

For example, if $n = 5,ドル feeding the interactor with $x = [2, 15, 7, 27, 8, 30]$ would cause 4ドル$ collisions in total:

Note that the interactor creates the hash table by inserting the elements in order into an initially empty unordered_set, and a new empty unordered_set will be created for each query. In other words, all queries are independent.

Your task is to find the number of buckets $n$ using total cost of at most 1ドル,円 000,円 000$.

구현 상세

You should implement the following procedure:

int hack()

• This procedure should return an integer – the hidden value of $n$.
• For each test case, the grader may call this function more than once. Each call should be processed as a separately new scenario.

Within this procedure, you may call the following procedure:

long long collisions(std::vector<long long> x)

• $x$: an array of distinct numbers, where 1ドル ≤ x[i] ≤ 10^{18}$ for each $i$.
• This function returns the number of collisions created by inserting the elements of $x$ to an unordered_set.
• This procedure can be called multiple times. The sum of length of $x$ over all calls within one call to hack() must not exceed 1ドル,円 000,円 000$.

Note: Since the procedure hack() will be called more than once, contestants need to pay attention to the impact of the remaining data of the previous call on the current call, especially the state stored in global variables.

The cost limit of 1ドル,円 000,円 000$ applies to each test case. In general, if there are $t$ calls to hack(), you may use a total cost of no more than $t \times 1,円 000,円 000,ドル with each individual call to hack() using a cost no more than 1ドル,円 000,円 000$.

The interactor is not adaptive, i.e. the values of $n$ are fixed before the start of interaction.

예제

Suppose, there are 2ドル$ multitests. The grader will make a following call:

hack()

Let's say, within the function, you make following calls:

After that, if you find that the value of $n$ is 5ドル,ドル the procedure hack() should return 5ドル$.

Then grader will make another call:

hack()

Let's say, within the function, you make following calls:

The only $n$ which satisfies the queries is 2ドル$. So, the procedure hack() should return 2ドル$.

입력

출력

제한

• 1ドル ≤ t ≤ 10,ドル where $t$ is the number of multitests.
• 2ドル ≤ n ≤ 10^9$
• 1ドル ≤ x[i] ≤ 10^{18}$ for each call to collisions().

서브태스크

힌트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $t$

Then, $t$ lines follow, each containing a value of $n$:

• line 1ドル$: $n$

For each test case, let $m$ be the return value of hack(), and $c$ be the total cost of all queries. The sample grader prints your answer in the following format:

• line 1ドル$: $m$ $c$

첨부

• hack.zip