B - Better Students Are Needed! Editorial by en_translator Editorial for printing
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: