Official

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: