Four Suits
Contest: Educational Codeforces Round 154 (Rated for Div. 2)
Difficulty rating: 3200
Tags: binary search, bitmasks, flows, greedy

The game of Berland poker is played as follows. There are $$$n+1$$$ people: $$$n$$$ players, numbered from $$$1$$$ to $$$n$$$, and the dealer. The dealer has a deck which contains cards of four different suits (the number of cards of each suit is not necessarily the same); the number of cards in the deck is divisible by $$$n$$$. The dealer gives all cards to the players, so that every player receives the same number of cards, and the whole deck is used.

After the cards are dealt, every player chooses one of four suits (independently) and discards all cards from their hand which do not belong to their chosen suit. The winner of the game is the player with the maximum number of cards left in their hand. The number of points the winner receives is $$$x - y$$$, where $$$x$$$ is the number of cards in the winner's hand, and $$$y$$$ is the maximum number of cards among all other players; everyone else receives $$$0$$$ points. Note that it means that if there are multiple players with the maximum number of cards, everyone receives $$$0$$$ points.

Since every player wants to maximize their odds to win, they will choose a suit with the maximum number of cards in their hand.

Monocarp is the dealer. He has already given some cards to the players; the $$$i$$$-th player received $$$a_{i,j}$$$ cards of suit $$$j$$$. Note that the number of cards in players' hands don't have to be the same at this moment. Monocarp has $$$b_1, b_2, b_3, b_4$$$ cards of suit $$$1, 2, 3, 4$$$ respectively left in his deck. He has to give them to the players so that, after all cards are dealt, every player has the same number of cards.

For each player, calculate the maximum number of points they can receive among all ways to deal the remaining cards according to the rules of the game.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^4$$$) — the number of players.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains four integers $$$a_{i,1}, a_{i,2}, a_{i,3}, a_{i,4}$$$ ($$$0 \le a_{i,j} \le 10^6$$$), where $$$a_{i,j}$$$ is the number of cards of the $$$j$$$-th suit that the $$$i$$$-th player currently has.

The last line contains $$$4$$$ integers $$$b_1, b_2, b_3, b_4$$$ ($$$0 \le b_j \le 10^6$$$), where $$$b_j$$$ is the number of cards of the $$$j$$$-th suit Monocarp has to deal yet.

Additional constraint on the input: it is possible to deal all of the remaining cards so that every player has the same number of cards.

Output format:
Print $$$n$$$ integers. The $$$i$$$-th of them should be the maximum number of points the $$$i$$$-th player can get among all possible ways to deal the remaining cards.

Constraints:
Time limit: 6.0 s
Memory limit: 1024.0 MB

Example input:
2
3 1 1 1
1 1 1 1
2 2 0 0

Example output:
1 0

Example input:
4
0 0 0 0
0 0 0 1
2 2 0 0
0 1 0 0
3 2 3 2

Example output:
1 1 1 1

Editorial:
As far as I am concerned, fully greedy solutions don't work in this problem. However, we can try employing some greedy ideas.
First of all, let's calculate how many cards each player should receive. I will call it $$$remain_i$$$ for the $$$i$$$-th player.
Suppose we want to maximize the answer for the $$$i$$$-th player. Let's iterate on the suit $$$j$$$ for which that player will have the maximum number of cards. We can assign as many cards of suit $$$j$$$ as possible from the deck to the $$$i$$$-th player: suppose we have given a card of suit $$$j$$$ to another player, and a card of another suit to the $$$i$$$-th player. If we exchange them, the answer won't become worse.
Okay, now we want to find the minimum possible maximum number of cards (after the players discard some of their cards) that the other players can have. Let's suppose it's $$$x$$$. There should be a way to assign the remaining cards from the deck so that every player $$$k$$$ gets exactly $$$remain_k$$$ cards, and no player has more than $$$x$$$ cards in any suit (except for the $$$i$$$-th player).
The good thing is that if it's possible to assign cards for some value of $$$x$$$, it's also possible for $$$x+1$$$. So, we can find this $$$x$$$ with binary search.
Now we have to solve the following problem: check if there exists an assignment of cards from the deck for a particular $$$x$$$. We can model it using maximum flow:
• create a network with a source, sink, a vertex for every player except for $$$i$$$, and a vertex for every suit;
• for every suit, create a directed edge from the source to that suit with capacity equal to the number of cards of that suit left in the deck (don't forget that we greedily assigned some cards to the $$$i$$$-th player!);
• for every player $$$k$$$ except $$$i = k$$$, create a directed edge from that player to the sink with capacity equal to $$$remain_k$$$;
• for every suit and every player except $$$i$$$, create a directed edge from the suit to the player with capacity equal to the maximum number of cards of that suit the player can receive;
• check that the maximum flow in this network saturates all edges going into the sink (i. e. is equal to the sum of $$$remain_k$$$ for all players except the $$$i$$$-th one).
However, simply building this network is too slow, let alone finding the maximum flow in it. We need something faster.
If you're thinking about using Hall's theorem, then unfortunately, it doesn't work since it cannot handle the constraint on $$$x$$$. But you're thinking in the right direction.
Let's try to find the minimum cut in this network. To do this, iterate on the $$$mask$$$ of the suits that will be in the set $$$S$$$ in the minimum cut, add the capacities of other suits to the value of the cut, and for every player, determine if it's better to have them in the set $$$S$$$ or in the set $$$T$$$ of the cut. The key thing is that if we fix the mask of suits and the value of $$$x$$$, it is uniquely determined. Let the number of suits in the mask be $$$suits$$$, and the total number of cards the $$$k$$$-th player has from those suits be $$$alreadyHas_{mask,k}$$$. The total capacity of all edges going into the $$$k$$$-th player that we need to cut is $$$suits \cdot x - alreadyHas_{mask,k}$$$, and the capacity of the outgoing edge is $$$remain_k$$$. So, the value the $$$k$$$-th player adds to the cut is $$$\min(remain_k, suits \cdot x - alreadyHas_{mask,k})$$$, and we need to compute the sum of these values for all players (except for the player $$$i$$$) efficiently.
This is basically the outline of the solution. Now the implementation part follows. To be honest, I think that the model solution is a bit too complicated, some solutions I've seen during the contest are shorter and cleaner. But I will explain it nevertheless.
For every $$$mask$$$ and every value of $$$x$$$, let's try to find the sum of $$$\min(suits \cdot x - alreadyHas_{mask,k}, remain_k)$$$ over all players. To do this, for every player, find the maximum value of $$$x$$$ such that $$$suits \cdot x - alreadyHas_{mask,k}$$$ is less than $$$remain_k$$$. For the value of $$$x$$$ not greater than this value, the player adds $$$suits \cdot x - alreadyHas_{mask,k}$$$ to the cut; for greater values, the player adds $$$remain_k$$$. Both of those are linear functions, and for every $$$x$$$, we can compute the sum of those linear functions for all players using difference arrays. I calculate these sums of linear functions in all values of $$$x$$$ up to $$$2 \cdot 10^6$$$, because there might be situations when a player has more than $$$10^6$$$ cards of a particular suit.
That way, when we want to compute the minimum cut for the $$$i$$$-th player, chosen mask of suits and the value of $$$x$$$, we can use the already computed sum of those functions to find the total value all players add to the cut, and then subtract the value that the $$$i$$$-th player added (since we need to discard that player from the network).
The rest of the implementation is fairly straightforward, you can see the reference code for details (I hope I commented it well enough). One final note: when choosing the left border for binary search, I compute the maximum number of cards among all suits that the other players have, to make sure that I don't choose the value of $$$x$$$ that leads to edges having negative capacity in the network. But I think it's not actually required, so you can try discarding it from the solution.
The model implementation works in something like $$$O(2^K \cdot (n \cdot K + A))$$$ for precalculation of linear functions plus $$$O(n \cdot 2^K \cdot K^2 \cdot \log A)$$$ for actually solving the problem, where $$$A$$$ is the maximum number of cards of a particular suit a player can have ($$$A \le 2 \cdot 10^6$$$).