← 返回 twosigma 的题目列表IPO Share Allocation
类型：online_judge
IPO Share Allocation
A company has totalShares shares available for an IPO. You are given a list of bids, where each bid has the form:
(userId, shares, price, timestamp)
userId is unique.
shares is the number of shares requested.
price is the offered price per share.
timestamp indicates when the bid was submitted; a smaller value means earlier submission.
Allocate shares using these rules:
Process bids with higher prices first.
For bids with the same price, sort them by increasing timestamp.
Within the same-price group, allocate shares in round-robin order: in each round, give one share to every bidder that still has unmet demand, until all bids in the group are fulfilled or no shares remain.
A user is unallotted if they receive fewer shares than requested.
Return all unallotted userId values in ascending order.
Input Format
n totalShares
userId_1 shares_1 price_1 timestamp_1
...
userId_n shares_n price_n timestamp_n
Output Format
Print unallotted user IDs in ascending order, separated by spaces. Print an empty line if every user is fully allotted.
Example
Input:
4 5
1 2 10 3
2 1 12 1
3 2 10 1
4 3 10 2
Output:
1 4
Example
Input
4 5
1 2 10 3
2 1 12 1
3 2 10 1
4 3 10 2
Output
1 4