ItsWhomYouKnow
SRM 834 · 2022-07-25 · by misof
Problem Statement
In Mafia City each person belongs to exactly one of C different clans. The clans are numbered from 0 to C-1.
A new doctor just arrived to Mafia City with his receptionist, Miss Susie. (They aren't in any clan, but that's not important.) Miss Susie is in charge of calling patients into the doctor's office.
The first day of their practice just started. There are already some people waiting in the doctor's waiting room. The arrays initialClans and initialPowers (with L elements each) describe these people in the order in which they arrived. The people have numbers from 0 to L-1, and for each person we know their clan (initialClans[i]) and their power (initialPowers[i]). More people will arrive during the day.
Miss Susie quickly understood that the local situation is different from her previous practice. Here, it does not matter how sick you are. Who arrived first matters somewhat, a person's power also matters a little, but neither of those two things is the most important one. It's whom you know. If someone is from a powerful clan, it's dangerous to keep them waiting for too long.
As Miss Susie observes the waiting patients, she is gradually learning new things about the clans. Miss Susie's opinion on the power of a clan is equal to the maximum of the powers of its members she already saw. (This includes those who are no longer in the waiting room.)
Whenever the doctor calls for a new patient, Miss Susie looks at all the waiting patients. Among their clans she selects the most powerful one (according to her current knowledge). In case of a tie, she prefers the clan with the smallest number among the tied ones. She invites in the member of that clan who has been waiting for the longest amount of time (i.e., the one with the smallest number).
In order to keep the input small, the new patients who arrive during the day are generated pseudorandomly. Please use the pseudocode below to generate a new patient.
function new_patient():
state = (state * 1103515245 + 12345) modulo 2^31
clan = (state div 10) modulo C
state = (state * 1103515245 + 12345) modulo 2^31
power = state modulo P
return (clan, power)
You are given the integer N.
Initialize the variable "state" to seed, and initialize the variable "answer" to zero.
Then, simulate N rounds of events. The rounds are numbered from 0 to N-1.
In round x, do the following:
- Two new patients arrive into the waiting room. Call new_patient() twice to generate them. Assign them the next two available numbers.
- The doctor calls for a new patient. Determine the number ID[x] of the patient Miss Susie calls into the office.
- answer += ID[x] * (x+1)
- state = (state + ID[x]) modulo 2^31
After the last round, return answer.
Notes
- The reference solution does not depend on the input being pseudorandom.
- For the constraints used in this problem it is guaranteed that answer won't overflow a signed 64-bit integer variable.
Constraints
- N will be between 1 and 100,000, inclusive.
- C will be between 1 and 10^6, inclusive.
- P will be between 1 and 10^9, inclusive.
- initialClans will have between 0 and 100 elements, inclusive.
- Each element of initialClans will be between 0 and C-1, inclusive.
- initialPowers will have the same number of elements as initialClans.
- Each element of initialPowers will be between 0 and P-1, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
5
10
1000
{}
{}
47
Returns: 51
The waiting room starts empty. Below is a full log of what happens during the five rounds: round 0: person number 0 (clan 0 power 405) enters the waiting room person number 1 (clan 9 power 91) enters the waiting room nurse calls in patient #0 answer incremented by 0 state at the end of the round is 160854091 round 1: person number 2 (clan 4 power 433) enters the waiting room person number 3 (clan 5 power 527) enters the waiting room nurse calls in patient #3 answer incremented by 6 state at the end of the round is 1993983530 round 2: person number 4 (clan 6 power 640) enters the waiting room person number 5 (clan 9 power 542) enters the waiting room nurse calls in patient #4 answer incremented by 12 state at the end of the round is 1965431546 round 3: person number 6 (clan 9 power 264) enters the waiting room person number 7 (clan 6 power 230) enters the waiting room nurse calls in patient #7 answer incremented by 28 state at the end of the round is 321580237 round 4: person number 8 (clan 3 power 531) enters the waiting room person number 9 (clan 8 power 1) enters the waiting room nurse calls in patient #1 answer incremented by 5 state at the end of the round is 176589002
3
10
1000
{4, 7, 1, 2, 4, 4, 0, 9}
{13, 2, 55, 17, 600, 0, 101, 100}
47
Returns: 44
Again, the full log of actions is shown below. Note that even though we started from the same seed, in round 2 the new people generated are no longer the same as in Example 0 (because ID[1] was different). person number 0 (clan 4 power 13) starts in the waiting room person number 1 (clan 7 power 2) starts in the waiting room person number 2 (clan 1 power 55) starts in the waiting room person number 3 (clan 2 power 17) starts in the waiting room person number 4 (clan 4 power 600) starts in the waiting room person number 5 (clan 4 power 0) starts in the waiting room person number 6 (clan 0 power 101) starts in the waiting room person number 7 (clan 9 power 100) starts in the waiting room round 0: person number 8 (clan 0 power 405) enters the waiting room person number 9 (clan 9 power 91) enters the waiting room nurse calls in patient #0 answer incremented by 0 state at the end of the round is 160854091 round 1: person number 10 (clan 4 power 433) enters the waiting room person number 11 (clan 5 power 527) enters the waiting room nurse calls in patient #4 answer incremented by 8 state at the end of the round is 1993983531 round 2: person number 12 (clan 6 power 609) enters the waiting room person number 13 (clan 0 power 399) enters the waiting room nurse calls in patient #12 answer incremented by 36 state at the end of the round is 1663867411
3
1000
1000
{123, 789, 456}
{999, 999, 999}
47
Returns: 7
The six new people are from clans other than 123, 456, and 789. As these three clans are tied for the highest power, the nurse will apply the tiebreaker rule: the nurse will first call patient #0 (clan 123), then patient #2 (clan 456) and only then patient #1 (clan 789).
3
10
1000
{4, 7, 1, 2, 4, 4, 6, 9}
{13, 2, 55, 17, 600, 0, 101, 100}
47
Returns: 26
100000
1000000
1000000000
{}
{}
47
Returns: 646138898940410
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ItsWhomYouKnow with a public method long long simulate(int N, int C, int P, vector<int> initialClans, vector<int> initialPowers, int seed) · 60 test cases · 2 s / 256 MB per case