E - Examination Editorial by evima
[1] Checking if the answer is \(-1\)
Let us first consider how to check if the objective is achievable at all by performing any number of swaps. Since it is optimal to assign a higher score to a person with a greater \(B_i\) (stricter requirement), the objective is achievable if and only if:
\(B_i \leq A_i\) for every \(i\) when \(A\) and \(B\) are sorted in ascending order.
This is probably the common first try, but we need to rephrase this condition a little.
For \(1 \leq t \leq 10^9\),
let \(cnt_t=(\) the number of \(i\) such that \(B_i\leq t\) \()-(\) the number of \(i\) such that \(A_i\leq t\) \()\).
Then, \(cnt_t \geq 0\) holds for every \(t\).
These two conditions are equivalent.
[2] Finding the maximum number of unswapped people
If \(B_i \leq A_i\) holds for every \(i\) already in the beginning, the answer is \(N\).
Otherwise, we have to find a set \(S\) of people whose scores are swapped that minimizes \(|S|\). \(S\) must contain all people with \(A_i<B_i\) in the beginning.
So, let us initialize \(S\) as the set of people with \(A_i<B_i\) in the beginning, and add other people to \(S\) one at a time until \(cnt_t \geq 0\) holds for every \(t\).
In what order should we add people?
Consider the minimum \(t\) such that \(cnt_t < 0\) at the moment. Then, we must add Person \(i\) such that \(B_i \leq t\) and \(t < A_i\). If there is no such person, the objective is unachievable. If there are multiple such people, the person \(i\) with the maximum \(A_i\) should be chosen, because \(B_i\) does not matter since we have chosen the minimum \(t\) such that \(cnt_t<0\).
This solution works in \(O(NlogN)\) time by using, say, a priority queue.
Sample implementation (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq1;
priority_queue<int> pq2;
map<int,int> mp;
int ans=N;
for(int i=0;i<N;i++){
int A,B; cin >> A >> B;
if(A<B){
mp[A]--; mp[B]++;
ans--;
}
else pq1.emplace(B,A);
}
int cnt=0;
for(auto x:mp){
while(!pq1.empty()&&pq1.top().first<=x.first){
pq2.push(pq1.top().second); pq1.pop();
}
cnt+=x.second;
while(cnt<0){
if(pq2.empty()||pq2.top()<=x.first){
cout << -1 << endl; return 0;
}
cnt++; ans--;
mp[pq2.top()]--; pq2.pop();
}
}
cout << ans << endl;
}
posted:
last update: