\((A_i+B_i,i)\) を \(1\) 要素目の降順に、 \(1\) 要素目が同じなら \(2\) 要素目の昇順にソートせよという問題であると捉えることができます。

各言語の機能として実装されているソートに対してソート用の比較関数を渡す方針(実装例1)のほか、 \((-(A_i+B_i),i)\) を辞書順昇順にソートするとみなす方針(実装例2)を取ることもできます。

出力の直前に番号を昇順ソートする必要があることに注意してください。

言語標準のソートが十分高速であれば、時間計算量は \(O(N \log N)\) です。

実装例1 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

bool comp(const pi &l,const pi &r){
  if(l.first!=r.first){return (l.first>r.first);}
  return (l.second<r.second);
}

int main(){
  int N,K;
  cin >> N >> K;
  vector<pi> vp(N);
  for(int i=1;i<=N;i++){
    int A,B;
    cin >> A >> B;
    vp.push_back({A+B,i});
  }
  sort(vp.begin(),vp.end(),comp);
  vector<int> res;
  for(int i=0;i<K;i++){res.push_back(vp[i].second);}
  sort(res.begin(),res.end());
  for(int i=0;i<K;i++){
    cout << res[i] << "\n";
  }
  return 0;
}

実装例2 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int N,K;
  cin >> N >> K;
  vector<pi> vp(N);
  for(int i=1;i<=N;i++){
    int A,B;
    cin >> A >> B;
    vp.push_back({-(A+B),i});
  }
  sort(vp.begin(),vp.end());
  vector<int> res;
  for(int i=0;i<K;i++){res.push_back(vp[i].second);}
  sort(res.begin(),res.end());
  for(int i=0;i<K;i++){
    cout << res[i] << "\n";
  }
  return 0;
}