Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

整数 $N, K$ と、長さ $N$ の整数列 $X = (X_0, X_1, \dots, X_{N-1})$ が与えられます。

整数の組 $(M, A, B)$ は、以下の条件をすべて満たすとき良い組と呼ばれます:

  • $1 \le M < 2^{30}$
  • すべての $k = 0, 1, \dots, N-1$ に対して、$X_k = \lfloor \frac{Ak + B}{M} \rfloor$ が成り立つ。

与えられた制約の下で、良い組の個数は有限であることが証明できます。この個数を $C$ とします。

$K \le C$ が成り立つかどうかを判定し、成り立つならば辞書順で $K$ 番目に小さい良い組を求めてください。

$T$ 個のテストケースが与えられます。それぞれのテストケースについて独立に解いてください。

入力

入力は以下の形式で与えられます:

T
case1
case2
:
caseT

各テストケース $\text{case}_i$ は以下の形式で与えられます:

N K
X0 X1 ... XN-1

制約

  • 入力される値はすべて整数である。
  • $1 \le T \le 1000$
  • $2 \le N \le 2 \times 10^5$
  • $1 \le K \le 10^9$
  • $0 \le X_i < 2^{30}$
  • すべてのテストケースにおける $N$ の総和は $2 \times 10^5$ を超えない。

出力

$T$ 行出力してください。

$i$ 行目には、$i$ 番目のテストケースにおいて $K \le C$ が成り立つならば、辞書順で $K$ 番目に小さい良い組の $M, A, B$ をこの順に空白区切りで出力してください。そうでないならば、-1 を出力してください。

入出力例

入力例 1

3
4 1
0 1 1 2
3 1
2 0 1
6 7
9 8 6 4 2 1

出力例 1

2 1 1
-1
11 -19 107

注記

最初の例では、辞書順での良い組は $(M, A, B) = (2, 1, 1), (3, 2, 1), (4, 2, 2), (4, 2, 3), (4, 3, 1), \dots$ です。

2 番目の例では、良い組は存在しません。

3 番目の例では、辞書順での良い組は $(M, A, B) = (4, -7, 39), (7, -12, 68), (8, -14, 78), (8, -14, 79), (9, -16, 89), (10, -17, 97), (11, -19, 107), \dots$ です。

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1416EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.