## Intuition The problem involves determining the winner of an auction after excluding certain participants. The key insight is to simulate the auction process by removing the bids of absent participants and ensuring no participant makes consecutive bids. The challenge is efficiently handling multiple queries about different sets of absent participants. ## Approach 1. **Preprocessing Bids**: - Store all bids in a list of pairs `(ai, bi)`, where `ai` is the participant index and `bi` is the bid value. - For each query, we need to determine the winner after excluding certain participants. 2. **Handling Queries**: - For each query, create a set of absent participants for quick lookup. - Traverse the list of bids, skipping any bid made by an absent participant. - Maintain a record of the last participant who made a valid bid to ensure no consecutive bids by the same participant. - Track the highest valid bid and the corresponding participant. 3. **Output**: - For each query, output the participant with the highest valid bid and the bid value. If no valid bids remain, output `0 0`. ## Complexity - **Time Complexity**: - Preprocessing the bids takes `O(n)`. - Each query involves traversing the bids, which is `O(n)`. Thus, the total complexity is `O(n + q * n)`. - **Space Complexity**: - The space used is `O(n)` for storing bids and `O(k)` for the set of absent participants per query. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector> bids(n); for (int i = 0; i < n; ++i) { cin >> bids[i].first >> bids[i].second; } int q; cin >> q; while (q--) { int k; cin >> k; unordered_set absent; for (int i = 0; i < k; ++i) { int l; cin >> l; absent.insert(l); } int last_person = -1; int max_bid = 0; int winner = 0; for (const auto& bid : bids) { int person = bid.first; int bid_value = bid.second; if (absent.count(person) == 0 && person != last_person) { if (bid_value > max_bid) { max_bid = bid_value; winner = person; } last_person = person; } } cout << winner << " " << max_bid << "\n"; } return 0; } ``` This solution efficiently processes each query by leveraging a set to track absent participants and iterating through the bids to determine the winner. The use of `unordered_set` ensures quick lookups for absent participants, and careful tracking of the last valid bidder prevents consecutive bids by the same participant.

Leaving Auction

Problem Details