B - Better Students Are Needed! Editorial by en_translator
Since \(N \le 1000\), we may scan all \(N\) examinees every time we determine one admitted examinee. We will omit the details.
This time, we will explain a trick to solve the problem by sorting integers.
First, we will explain how to determine the admitted examinees in step 1.
Consider the values \(C_i = 10000 \times (100-A_i) + i\) and sort the examinees by these values.
For example, when \(A=(95,70,100,85)\), we have \(C=(50001,300002,3,150004)\). After sorting, this becomes \((3,50001,150004,300002)\). (Note that the remainder of \(C_i\) divided by \(10000\) corresponds to the examinees’ number.)
By sorting \(C_i\), the examinees are sorted by (the decreasing order of \(A_i\)) \(\rightarrow\) (the increasing order of examinees’ numbers).
Reason: the difference of examinees’ numbers are at most \(999\). On the other hand, if the score \(A_i\) differs by \(1\), \(C_i\) differs by \(10000\), resulting in a sort where the scores \(A_i\) are prioritized.
We can do the same thing in the succeeding steps to get accepted for the problem.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,x,y,z;
cin >> n >> x >> y >> z;
vector<int> a(n+5),b(n+5);
for(int i=1;i<=n;i++){cin >> a[i];}
for(int i=1;i<=n;i++){cin >> b[i];}
vector<bool> passed(n+5,false);
vector<int> c;
for(int i=1;i<=n;i++){
c.push_back(10000*(100-a[i])+i);
}
sort(c.begin(),c.end());
for(int i=0;i<x;i++){
passed[c[i]%10000]=true;
}
c.clear();
for(int i=1;i<=n;i++){
if(!passed[i]){
c.push_back(10000*(100-b[i])+i);
}
}
sort(c.begin(),c.end());
for(int i=0;i<y;i++){
passed[c[i]%10000]=true;
}
c.clear();
for(int i=1;i<=n;i++){
if(!passed[i]){
c.push_back(10000*(200-(a[i]+b[i]))+i);
}
}
sort(c.begin(),c.end());
for(int i=0;i<z;i++){
passed[c[i]%10000]=true;
}
for(int i=1;i<=n;i++){
if(passed[i]){cout << i << "\n";}
}
return 0;
}
posted:
last update: