409609: GYM103643 L Circle Game

Codicon has gotten into gambling (uh oh!). He plays a game containing $$$3 \leq N \leq 2 \cdot 10^5$$$ players (including himself) seated in a circle in positions $$$1$$$ to $$$N$$$ going clockwise, where Codicon is in the first position. At the beginning of the game, each player is assigned a number, and during each of $$$1 \leq R \leq 2 \cdot 10^5$$$ rounds two selected players (that are not Codicon) switch spots. Codicon then bets a certain amount of money $$$b$$$ in each round that his number is below at least half of the other people who are at most $$$K$$$ seats away from him ($$$1 \leq K < \left\lceil \frac{N}{2} \right\rceil$$$). If he wins the bet he gets $$$b$$$ $$$(1 \leq b \leq 10^6)$$$ dollars, otherwise he loses $$$b$$$ dollars.

In addition, since Codicon is the person that is betting, in each round his number changes before he bets. Given that he starts with $$$M$$$ $$$(1 \leq M \leq 10^9)$$$ dollars output the amount of money he ends up with after all $$$R$$$ rounds, if he loses all his money or goes into debt, output "BANKRUPT" and the round number in which he lost his money (i.e. If Codicon goes bankrupt on the third round output BANKRUPT 3).

The first line contains $$$N, R, M, K$$$ in that order.

The next line has $$$N$$$ integers, corresponding to the assigned number $$$a_i$$$ $$$(1 \leq a_i \leq N)$$$ each player gets.

The last $$$R$$$ lines each have $$$s_r, t_r, n_{r}, b_r$$$, where in the $$$r$$$th round, the players in spots $$$s_r$$$ and $$$t_r$$$ $$$(s_r \neq t_r$$$ and $$$s_r, t_r \neq 1)$$$ are swapped, Codicon is assigned the number $$$n_{r}$$$ $$$(1 \leq n_{r} \leq N)$$$, and he bets $$$b_r$$$ dollars for that round.

Test case 1 is the sample and will not be worth points.

Test cases 2-4: $$$N \leq 1000$$$

Test cases 5-21: No further restrictions

A single integer that shows how much money Codicon ended up with after he finished all the rounds, or if he loses all his money output "BANKRUPT" and the round number in which he lost all his money (i.e. BANKRUPT 3).

5 3 200 1
2 3 1 4 4
2 3 5 10
4 2 2 40
4 5 3 30

260

Note that since $$$K = 1$$$, Codicon looks to the people sitting next to him to see if he won the bet. For the first round, players in position $$$2$$$ and $$$3$$$ switch places and Codicon's number switches to $$$5$$$, which is greater than the number of both people sitting next to him ($$$4$$$ and $$$1$$$), so he loses $$$10$$$ dollars. He then wins the next two rounds, so he ends up with $$$260$$$ dollars.

$$$---------------------------------------------$$$

Problem Idea: Bossologist

Problem Preparation: Bossologist

Occurrences: Intermediate 9, Advanced 5