레이팅 미적용3
Everybody is very happy to go back outside and to restaurants in Paris. However, for a while yet the restaurants have a very limited number of seats. We want to ensure that both restaurants can receive as many people as possible, and that customers go in their preferred seats.
We have \(N\) customers, numbered from \(1\) to \(N\), and \(M\) restaurants, numbered from \(1\) to \(M\).
Each customer makes reservation in a subset of the restaurants, and give their list of reservations ordered by preference. Each restaurant ranks the reservations it received by some order of preference – for instance, the restaurant might wish customers who have signed up first to be ranked higher. Each restaurant \(i\) also has a capacity \(c_i\), i.e. the maximal number of customers it can support.
Your task is to find an allocation of some of the customers in restaurants such that the following conditions are fulfilled:
- No restaurant places more customers than their capacity.
- Each customer is given a table in at most one restaurant.
- There is no other possible allocation of a customer to a restaurant so that both sides prefer it to the current allocation.
- There is no restaurant \(r\) and customer \(c\) having made a reservation for \(r\), such that:
- \(c\) has not been given a table or prefers \(r\) to the restaurant he was given a table in, and
- \(r\) has some seats left or \(r\) is full but prefers \(c\) to at least one of the customers assigned to it.
Other remarks to note:
- Every customer has made at least one reservation.
- Restaurants only rank the customers having expressed a reservation for them. It is possible that a restaurant has no customers wishing to make a reservation.
The first line contains \(N\) and \(M\).
The \(M\) following lines describe capacities with the \(i\)-th line containing an integer \(c_i\), the capacity of restaurant \(i\).
\(N\) lines follow. The \(i\)-th line describes the list of reservations for customer \(i\), sorted by preferences: the line contains a list of distinct space-separated integers (between 1 and \(M\)), from most to least preferred.
\(M\) lines follow. The \(i\)-th line describes the sorted preferences of restaurant \(i\). This line contains either the number 0 when no customer made a reservation to restaurant \(i\) or it contains a list of space-separated distinct integers, the list of customers who made a reservation to restaurant \(i\) ordered from most to least preferred by the restaurant.
The output described the set of customers which have a table in one possible allocation (according to the rules above). The set is given with one customer per line, sorted ascending by id.
4 4
2
2
2
1
2
2 3
2 1 3
1 2 4 3
3 4
3 2 4 1
3 4 2
4
2
3
4