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$입니다.

두 번째 예제에서는 좋은 순서쌍이 존재하지 않습니다.

세 번째 예제에서 사전순으로 나열한 좋은 순서쌍은 $(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.