← 返回 twosigma 的题目列表IPO Allocation with Price Group Round-Robin and Timestamp Tie-Breaking
类型：online_judge
You are given a list of IPO orders. Each order contains:
orderId: unique identifier
price: bid price (integer)
timestamp: submission time (integer; smaller means earlier)
quantity: requested shares (integer)
You are also given totalShares, the total number of shares available to allocate.
Allocate shares according to the following rules and output the final allocated shares for each order (e.g., orderId -> allocatedShares):
Process orders by price descending.
For each same-price group, sort orders by timestamp ascending (earlier orders enter the rotation first).
Within the same-price group, allocate using round-robin:
When an order is visited, if it still needs shares (remaining > 0) and there are shares left, allocate 1 share to it.
Move to the next order and repeat cyclically.
Stop when all orders in the group are fully satisfied or totalShares is exhausted.
If shares remain, continue to the next lower price group.
Implement this allocation.
Input (stdin):
Line 1: two integers n totalShares
Next n lines: orderId price timestamp quantity
Output (stdout):
Print n lines: orderId allocatedShares, sorted by orderId ascending.
Constraints (typical):
1 <= n <= 2e5
0 <= totalShares <= 1e9
1 <= price, quantity <= 1e9
0 <= timestamp <= 1e9
Example
Input:
3 4
101 10 1 3
102 10 2 3
103 9 3 5
Output:
101 2
102 2
103 0
Explanation:
Two orders at price 10 are rotated by timestamp, receiving 2 shares each.
Shares are exhausted; price 9 gets 0.
Example
Input
3 4
101 10 1 3
102 10 2 3
103 9 3 5
Output
101 2
102 2
103 0