Sum Within Shortest Span

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
Châu Nhật Tăng
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

One day, Jack stumbled upon a mysterious sequence of ~N~ integers. Curious as always, he was given a secret number ~S~ by his friend and challenged to find a contiguous subarray within the sequence whose sum is exactly ~S~. However, Jack is not a fan of long segments — he only wants the shortest possible subarray that satisfies this condition.

If multiple such shortest subarrays exist, you may return any of them. If no such subarray exists, Jack will accept a simple -1.

Your task is to help Jack find the shortest contiguous subarray with a sum exactly equal to ~S~, and print both its length and elements.

Input

  • The first line contains two integers ~N~ and ~S~ — the number of elements in the array and the target sum ~(1 ≤ N ≤ 10^5, |S| ≤ 10^9)~.
  • The second line contains ~N~ integers — the array elements ~A_1, A_2, ..., A_N~ where ~( |A_i| ≤ 10^9 )~.

Output

  • If a valid subarray exists:
    • The first line should print the length of the subarray.
    • The second line should print the elements of the subarray (space-separated).
  • If no such subarray exists, print ~-1~.

Sample Input

9 15
13 3 6 0 -3 4 13 -5 3

Sample Output

4
4 13 -5 3

Notes

  • You will receive ~50\%~ of the points for each test case if you can find a subsequence whose sum equals ~S~.
  • You will receive the remaining ~100\%~ of the points if you can find the shortest such subsequence whose sum equals ~S~.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.