作者： chenchen

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed N(2≤N≤10⁵) cows for the position. After interviewing the i
th candidate, he assigned the candidate an integer "cowmpetency" score c_i
ranging from 1 to C inclusive (1≤C≤10⁹) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John does not remember all of their cowmpetency scores. However, he does remembers Q (1≤Q<N) pairs of numbers (a_j,h_j) where cow h_j was the first cow with a strictly greater cowmpetency score than cows 1 through a_j (so 1≤a_j<h_j≤N).

Farmer John now tells you the sequence c₁,…,c_N (where c_i=0 means that he has forgotten cow i's cowmpetency score) and the Q pairs of (a_j,h_j). Help him determine the lexicographically smallest sequence of cowmpetency scores consistent with this information, or that no such sequence exists! A sequence of scores is lexicographically smaller than another sequence of scores if it assigns a smaller score to the first cow at which the two sequences differ.

Each input contains T (1≤T≤20) independent test cases. The sum of N across all test cases is guaranteed to not exceed 3⋅10⁵.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of independent test cases. Each test case is described as follows:

First, a line containing N, Q, and C.
Next, a line containing the sequence c₁,…,c_N (0≤c_i≤C).
Finally, Q lines each containing a pair (a_j,h_j). It is guaranteed that all a_j within a test case are distinct.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a single line containing the lexicographically smallest sequence of cowmpetency scores consistent with what Farmer John remembers, or −1 if such a sequence does not exist.

SAMPLE INPUT:

1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5

SAMPLE OUTPUT:

1 2 2 3 4 4 1

We can see that the given output satisfies all of Farmer John's remembered pairs.
max(c1)=1, c2=2 and 1<2 so the first pair is satisfied
max(c1,c2,c3)=2, c4=3 and 2<3 so the second pair is satisfied
max(c1,c2,c3,c4)=3, c5=4 and 3<4so the third pair is satisfied

There are several other sequences consistent with Farmer John's memory, such as
1 2 2 3 5 4 1
1 2 2 3 4 4 5

However, none of these are lexicographically smaller than the given output.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1

In test case 3, since C=1, the only potential sequence is

1 1

However, in this case, cow 2 does not have a greater score than cow 1, so we cannot satisfy the condition.

In test case 5,a₁and h₁ tell us that cow 6 is the first cow to have a strictly greater score than cows 1 through 4. Therefore, the largest score for cows 1 through 6 is that of cow 6: 5. Since cow 7 has a score of 7, cow 7 is the first cow to have a greater score than cows 1 through 6. So, the second statement that cow 9 is the first cow to have a greater score than cows 1 through 6 cannot be true.

SCORING:

Input 3 satisfies N≤10 and Q,C≤4.
Inputs 4-8 satisfy N≤1000.
Inputs 9-12 satisfy no additional constraints.
Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of N (1≤N≤2⋅10⁵) integers a₁,a₂,…,a_N (1≤a_i≤10¹¹) that she will put in a separate array in sorted order. She repeatedly finds the minimum integer in her pile, removes it, and adds it to the end of the array. It takes Bessie p seconds to find the minimum integer in a pile of p integers.

Farmer John instructed some of the other cows in the farm to help Bessie with her task, but they are quite lazy, so Bessie uses that to her advantage. She divides the integers into two piles: Bessie pile and Helper pile. For every integer in Bessie's pile, she performs her algorithm as normal. For every integer in the helper pile, she assigns it to a different helper cow. Farmer John has a large farm, so Bessie can get as many helper cows as she wants. If a helper receives the integer a_i, Bessie instructs that cow to nap for a_i seconds, and add their integer to the end of the array immediately when they wake up. If Bessie and a helper add an integer to the array at the same time, Bessie's integer will get added first since she is the leader. If more than one helper gets assigned the same integer, they will add copies of that integer to the array at the same time.

Help Bessie divide her integers so that the final array is sorted and the time it takes to sort the array is minimized.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of independent test cases (1≤T≤10).

Each test case is formatted as follows:

The first line of each test case contains the number of integers N in Bessie's array.

The next line of each test case contains a₁,a₂,…,a_N, the integers that Bessie is sorting. The same integer may appear multiple times.

It is guaranteed that the sum of N over all tests does not exceed 2⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the minimum time to sort the array on a new line, if Bessie divides her integers optimally.

SAMPLE INPUT:

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

SAMPLE OUTPUT:

6
15
5
6

In the first example, Bessie can assign 1,2 to helpers and leave 4,5,10¹¹ for herself.

In the second example, the best Bessie can do is sort everything by herself. One division that does *not* work is for Bessie to assign 4 to a helper and the rest to herself because Bessie will end up adding 17 to the array before the helper adds 4
to the array.

In the third example, Bessie can assign all the integers to helpers.

In the fourth example, Bessie can assign 1,4,5 to helpers and leave 2,5,100
to herself.

SCORING:

Input 2: N≤16
Inputs 3-5: N≤150
Inputs 6-8: ∑N≤5000
Inputs 9-11: No additional constraints.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed N (2≤N≤10⁹) cows for the position. After each interview, he assigned an integer "cowmpetency" score to the candidate ranging from 1
to C(1≤C≤10⁴) that is correlated with their leadership abilities.

Because he has interviewed so many cows, Farmer John has forgotten all of their cowmpetency scores. However, he does remembers Q(1≤Q≤min(N−1,100)) pairs of numbers (a_i,h_i) where cow h_i was the first cow with a strictly greater cowmpetency score than cows 1 through a_i (so 1≤a_i<h_i≤N).

Farmer John now tells you the Q pairs of (a_i,h_i). Help him count how many sequences of cowmpetency scores are consistent with this information! It is guaranteed that there is at least one such sequence. Because this number may be very large, output its value modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N, Q, and C.
The next Q lines each contain a pair (a_i,h_i). It is guaranteed that all a_j are distinct.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of sequences of cowmpetency scores consistent with what Farmer John remembers, modulo 10⁹+7.

SAMPLE INPUT:

6 2 3
2 3
4 5

SAMPLE OUTPUT:

6

The following six sequences are the only ones consistent with what Farmer John remembers:

1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3

SAMPLE INPUT:

10 1 20
1 3

SAMPLE OUTPUT:

399988086
Make sure to output the answer modulo 10⁹+7.

SCORING:

Inputs 3-4 satisfy N≤10 and Q,C≤4.
Inputs 5-7 satisfy N,C≤100.
Inputs 8-10 satisfy N≤2000 and C≤200.
Inputs 11-15 satisfy N,C≤2000.
Inputs 16-20 satisfy no additional constraints.
Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John and his Q(1≤Q≤2⋅10⁵) cows are in Manhattan on vacation, but the cows have escaped and are now walking around freely in the city! Manhattan is huge – so huge that its N (1≤N≤2⋅10⁵) roads stretch infinitely in the x-y plane, but conveniently, those roads all run perfectly horizontally or vertically. Each horizontal and vertical road can be modeled by an equation of the form y= c_i or x=c_i , where c_i  is an integer in the range 0 to 10⁹ inclusive.

Farmer John knows exactly where each cow started walking and how long ago they escaped. Cows are very predictable, so each of them walks according to the following pattern:

They only walk north (+y) or east (+x) at one unit per second.
If they are currently on a single road, they continue walking along the road's direction.
If they are at the intersection of two roads, they walk north if they have been walking for an even number of seconds and east otherwise.

Given the layout of Manhattan and the information for each cow, help Farmer John determine where his cows are now!

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and Q.

The next N lines describe the roads. Each road is described by a direction (H or V) and a coordinate c_i. It is guaranteed that the roads are unique.

The next Q lines describe the cows. Each cow is described by three integers (x_i,y_i,d_i), meaning that they started walking from (x_i,y_i) exactly d_i seconds ago. It is guaranteed that (x_i,y_i) lies on some road, and 0≤x_i,y_i,d_i≤10⁹ .

OUTPUT FORMAT (print output to the terminal / stdout):

Output Q lines, where the ith line contains the current position of the ith cow.

SAMPLE INPUT:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

SAMPLE OUTPUT:

14 5
7 13
6 15
6 16
110 4

The first two cows took the following paths:
(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

SCORING:
Inputs 2-4 satisfy N,Q,c_i,x_i,y_i,d_i≤100.
Inputs 5-9 satisfy N,Q≤3000.
Inputs 10-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Farmer John has N cows on his farm (2≤N≤2⋅10⁵), conveniently numbered 1…N
. Cow i is located at integer coordinates (x_i,y_i) (1≤x_i,y_i≤N). Farmer John wants to pick two teams for a game of mooball!

One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the N cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as x=0.5. FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true.

Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains a single integer N.

The next N lines of input each contain two space-separated integers x_i and y_i. It is guaranteed that the x_i form a permutation of 1…N, and same for the y_i.

OUTPUT FORMAT (print output to the terminal / stdout):

A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo 10⁹+7.

SAMPLE INPUT:
2
1 2
2 1

SAMPLE OUTPUT:
2
We can either choose the red team to be cow 1 and the blue team to be cow 2, or the other way around. In either case, we can separate the two teams by a net (for example, x=1.5).

SAMPLE INPUT:

3
1 1
2 2
3 3

SAMPLE OUTPUT:

10

Here are all ten possible ways to place the cows on teams; the ith character denotes the team of the ith cow, or . if the ith cow is not on a team.

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

SAMPLE INPUT:

3
1 1
2 3
3 2

SAMPLE OUTPUT:

12

Here are all twelve possible ways to place the cows on teams:

RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR

SAMPLE INPUT:

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

SAMPLE OUTPUT:

441563023

Make sure to output the answer modulo 109+7.

SCORING:

Input 5: N≤10
Inputs 6-9: N≤200
Inputs 10-13: N≤3000
Inputs 14-24: No additional constraints.
Problem credits: Dhruv Rohatgi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

**Note: The memory limit for this problem is 512MB, twice the default.**

Bessie is having fun playing a famous online game, where there are a bunch of cells of different labels and sizes. Cells get eaten by other cells until only one winner remains.

There are N (2≤N≤5000) cells in a row labeled 1…N from left to right, with initial sizes s₁,s₂,…,s_N (1≤s_i≤10⁵). While there is more than one cell, a pair of adjacent cells is selected uniformly at random and merged into a single new cell according to the following rule:

If a cell with label a and current size c_a is merged with a cell with label b and current size c_b , the resulting cell has size c_a +c_b and label equal to that of the larger cell, breaking ties by larger label. Formally, the label of the resulting cell is

For each label i in the range 1…N , the probability that the final cell has label i
can be expressed in the form where b_i≢0 ( mod 10⁹+7). Output a_ib⁻¹_i ( mod 10⁹+7).

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.
The next line contains s₁,s₂,…,s_N

OUTPUT FORMAT (print output to the terminal / stdout):

The probability of the final cell having label i modulo 10⁹+7
for each i in 1…N on separate lines.

SAMPLE INPUT:

3
1 1 1

SAMPLE OUTPUT:

0
500000004
500000004

There are two possibilities, where (a,b)→c means that the cells with labels a and b merge into a new cell with label c.

(1, 2) -> 2, (2, 3) -> 2
(2, 3) -> 3, (1, 3) -> 3

So with probability 1/2 the final cell has label 2 or 3.

SAMPLE INPUT:

4
3 1 1 1

SAMPLE OUTPUT:

666666672
0
166666668
166666668
The six possibilities are as follows:

(1, 2) -> 1, (1, 3) -> 1, (1, 4) -> 1
(1, 2) -> 1, (3, 4) -> 4, (1, 4) -> 1
(2, 3) -> 3, (1, 3) -> 1, (1, 4) -> 1
(2, 3) -> 3, (3, 4) -> 3, (1, 3) -> 3
(3, 4) -> 4, (2, 4) -> 4, (1, 4) -> 4
(3, 4) -> 4, (1, 2) -> 1, (1, 4) -> 1

So with probability 2/3 the final cell has label 1, and with probability 1/6
the final cell has label 3 or 4.

SCORING:

Input 3: N≤8
Inputs 4-8: N≤100
Inputs 9-14: N≤500
Inputs 15-22: No additional constraints.
Problem credits: Benjamin Q_i

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is taking a vacation in a network of N(2≤N≤10⁴) islands labeled 1…N
connected by M bidirectional bridges, each of which connects two islands (N−1≤M≤3/2(N−1)). It is guaranteed that the bridges form a connected simple graph (in particular, no two bridges connect the same pair of islands, and no bridge connects an island to itself).

It is also guaranteed that no bridge lies on more than one simple cycle. A simple cycle is a cycle that does not contain repeated islands.

Bessie starts at island 1, and travels according to the following procedure. Supposing she is currently at island i,

1.If there are no bridges adjacent to island i that she has not yet crossed, she ends her vacation.
2.Otherwise, with probability pi(mod 10⁹+7), she ends her vacation.
3.Otherwise, out of all bridges adjacent to island i that she has not yet crossed, she chooses one uniformly at random and crosses it.

For each island, output the probability that she ends her vacation at that island, modulo 10⁹+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains the number of independent test cases T (1≤T≤10). Consecutive test cases are separated by an empty line.

The first line of each test contains N and M, where N is the number of islands and M is the number of bridges. It is guaranteed that the sum of N over all test cases does not exceed 10⁴.

The second line of each test contains p₁,p₂,…,p_N (0≤p_i<10⁹+7).

The next M lines of each test describe the bridges. The ith line contains integers ui and vi (1≤u_i<v_i≤N), meaning that the ith bridge connects islands u_i and v_i. It is guaranteed that the bridges satisfy the constraints mentioned above.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output the probability of ending at each island from 1
to N modulo 10⁹+7 on a single line, separated by spaces.

SAMPLE INPUT:
2

3 2
0 10 111111112
1 3
2 3

6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 2

SAMPLE OUTPUT:

0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

For the first test case,p₃≡1/9(mod 10⁹+7). Bessie has probability 1/9
of ending at 3(taking the path 1→3) and 8/9of ending at 2(taking the path 1→3→2).

For the second test case, p₁ ≡1/2(mod 10⁹+7). Bessie has probability 1/2
of ending at 1, 1/6 of ending at each of 2
or 3, and 1/12 of ending at each of 4 or 6.

SAMPLE INPUT:
2

5 5
333333336 333333336 0 0 0
1 2
2 3
3 4
4 5
1 5

5 5
0 0 0 0 0
1 2
2 3
2 4
1 4
1 5

SAMPLE OUTPUT:

777777784 222222224 0 0 0
0 0 333333336 0 666666672

For the first test case, p₁ ≡p₂≡1/3(mod 10⁹+7). Bessie has probability 7/9
of ending at 1 (taking one of the paths 1, 1→2→3→4→5→1, or 1→5→4→3→2→1) and 2/9 of ending at 2.

For the second test case, Bessie has probability 1/3 of ending at 3, and 2/3 of ending at 5.

SAMPLE INPUT:

1

11 13
2 3 4 5 6 7 8 9 10 11 12
1 2
1 3
2 3
2 4
4 5
2 5
4 8
5 9
2 6
6 7
2 7
6 10
5 11

SAMPLE OUTPUT:

133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

SCORING:

Inputs 4-5: N≤11
Inputs 6-7: There are no simple cycles.
Inputs 8-11: No island lies on more than one simple cycle.
Inputs 12-15: No island lies on more than 5 simple cycles.
Inputs 16-19: No island lies on more than 50 simple cycles.
Inputs 20-23: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划