DMOPC '21 Contest 8 P1 - Peanut Planning - DMOJ: Modern Online Judge

DMOPC '21 Contest 8 P1 - Peanut Planning

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

It is well-known that Anya likes peanuts.

As the head of the city planning department, you have been tasked with planning the construction of a line of $N$ ~N~ peanut shops. The shops will have stocks of $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~ peanuts in some order.

Her father however, who you know as Loid Forger, is not a man known for his patience with Anya, and as such will only go to two peanut shops that are side-by-side.

This is fine by Anya as long as she can buy at least $M$ ~M~ peanuts, no matter which two adjacent shops they visit. If the two shops do not have enough stock, she will be quite distraught.

It turns out that of all plans that satisfy Anya's requirement, the lexicographically smallest one is the cheapest. You have been tasked to find the cheapest arrangement to make Anya happy, or sadly report that none exist.

Constraints

$2 \le N \le 5 \times 10^5$ ~2 \le N \le 5 \times 10^5~

$1 \le M \le 10^9$ ~1 \le M \le 10^9~

$1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~

Subtask 1 [20%]

$1 \le a_i \le 2$ ~1 \le a_i \le 2~

$M = 3$ ~M = 3~

Subtask 2 [30%]

$2 \le N \le 5 \times 10^3$ ~2 \le N \le 5 \times 10^3~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain $2$ ~2~ space-separated integers $N$ ~N~ and $M$ ~M~.

The second line will contain $N$ ~N~ space-separated integers, the list of shop stocks.

Output Specification

Output the lexicographically smallest array of stocks as specified by the problem. If there is no such array, output -1.

Scoring

You will receive 50% of the points for a case if your program outputs an array that satisfies Anya but that is not the cheapest.

Sample Input 1

4 8
2 6 10 1

Sample Output 1

1 10 2 6

Explanation for Sample 1

The adjacent sums are 11 12 8, which are all at least $M$ ~M~. It can be proven that this is the lexicographically smallest such arrangement.

Sample Input 2

4 9
2 6 10 1

Sample Output 2

-1

Explanation for Sample 2

It can be proven that no arrangement will make Anya happy.

Comments

0

Ze commented on May 16, 2022, 10:11 p.m.

Can someone look at my submissions and explain why I'm getting TLE for the 1st batch but all AC on the second batch? I tried linear and binary searching so I feel like it's my while loop, but I tested both methods and it works just fine.

0

andy_zhu23 commented on May 16, 2022, 10:23 p.m.

I believe vector erase has linear time complexity. Try to use multiset or map

3

John commented on April 28, 2022, 4:54 p.m.

You have good taste in anime

8

codicon commented on April 26, 2022, 5:01 a.m.

waku waku!