stable_sort()をしているのに安定ソートが出来ない

Question

問題
ABC260 B問題

正解コード（Python3）
ソートの順番は、優先度の低いものから先にやっていくという方針です。

N, X, Y, Z = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = []

passed = {}
for i in range(N):
	passed[i + 1] = False

score1 = []
for i in range(N):
	score1.append([A[i], B[i], A[i] + B[i], i + 1])
score1.sort(key = lambda x: x[3], reverse = True)
score1.sort(key = lambda x: x[0])
L1 = len(score1)
for i in range(L1 - 1, L1 - X - 1, -1):
	passed[score1[i][3]] = True
	ans.append(score1[i][3])

score2 = []
for i in range(L1):
	if passed[score1[i][3]] == False:
		score2.append(score1[i])
score2.sort(key = lambda x: x[3], reverse = True)
score2.sort(key = lambda x: x[1])
L2 = len(score2)
for i in range(L2 - 1, L2 - Y - 1, -1):
	passed[score2[i][3]] = True
	ans.append(score2[i][3])

score3 = []
for i in range(L2):
	if passed[score2[i][3]] == False:
		score3.append(score2[i])
score3.sort(key = lambda x: x[3], reverse = True)
score3.sort(key = lambda x: x[2])
L3 = len(score3)
for i in range(L3 - 1, L3 - Z - 1, -1):
	ans.append(score3[i][3])

ans.sort()
for el in ans:
	print(el)

不正解コード（C++17）
上のPythonのアルゴリズムと全く同じ方針でC++で行おうとしたものです。

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long

/* import vector from standard input */
vector<ll> import_vector(ll n) { vector<ll> li; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; }

void solve() {
	ll N, X, Y, Z; cin >> N >> X >> Y >> Z;
	vector<ll> A = import_vector(N);
	vector<ll> B = import_vector(N);

	map<ll, bool> passed = {};
	for (ll i = 1; i < N + 1; i++) {
		passed[i] = false;
	}

	vector<ll> ans = {};

	vector<vector<ll>> score1 = {};
	for (ll i = 0; i < N; i++) {
		score1.push_back({A.at(i), B.at(i), A.at(i) + B.at(i), i + 1});
	}

	sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];});
	reverse(score1.begin(), score1.end());
	sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];});
	ll L1 = score.size();
	for (ll i = L1 - 1; i >= L1 - X; i--) {
		passed[score1.at(i).at(3)] = true;
		ans.push_back(score1.at(i).at(3));
	}

	vector<vector<ll>> score2 = {};
	for (ll i = 0; i < score.size(); i++) {
		if (passed[score1.at(i).at(3)] == false) {
			score2.push_back(score1.at(i));
		}
	}

	sort(score2.begin(), score2.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];});
	reverse(score2.begin(), score2.end());
	sort(score2.begin(), score2.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[1] < beta[1];});
	ll L2 = score2.size();
	for (ll i = L2 - 1; i >= L2 - Y; i--) {
		passed[score2.at(i).at(3)] = true;
		ans.push_back(score2.at(i).at(3));
	}

	vector<vector<ll>> score3 = {};
	for (ll i = 0; i < score2.size(); i++) {
		if (passed[score2.at(i).at(3)] == false) {
			score3.push_back(score2.at(i));
		}
	}

	sort(score3.begin(), score3.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];});
	reverse(score3.begin(), score3.end());
	sort(score3.begin(), score3.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[2] < beta[2];});
	ll L3 = score3.size();
	for (ll i = L3 - 1; i >= L3 - Z; i--) {
		ans.push_back(score3.at(i).at(3));
	}

	sort(ans.begin(), ans.end());
	for (ll el: ans) {
		cout << el << endl;
	}
}

int main() {
    solve();
}

改善策と質問
後者がうまくいかなかった理由として、C++のSTLで実装されるsort()が安定ソートではなく不安定ソートである為、ケースによっては受験者の番号の順序を保存したまま点数を並び替え出来ないからと推測しています。そうであるとした場合そこで、例えば

sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];});
reverse(score1.begin(), score1.end());
sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];});

を

stable_sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[3] < beta[3];});
reverse(score1.begin(), score1.end());
stable_sort(score1.begin(), score1.end(), [] (vector<ll> &alpha, vector<ll> &beta) {return alpha[0] < beta[0];});

としようとしたのですが、ラムダ関数をstable_sort()には使えないとコンパイルエラーが起きました。このような場合、どのようにすれば所望の出力を得られるのでしょうか。素人質問にて恐縮ですが、お力添え頂ける箇所が御座いましたら、ご教授のほど宜しくお願い申し上げます。

追記）このようにソート関数を自作しても同じテストケースで引っかかり駄目でした：

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long

/* import vector from standard input */
vector<ll> import_vector(ll n) { vector<ll> li; for (ll i = 0; i < n; i++) { ll j; cin >> j; li.push_back(j); } return li; }

/* sorted(li, key = lambda x: x[K], ascending = x) */
vector<vector<ll>> key_sort(vector<vector<ll>> li, ll K, bool x) {
	vector<vector<ll>> ans = {};
	for (ll i = 0; i < li.size(); i++) {
		ans.push_back(li.at(i));
	}
	for (ll i = 0; i < ans.size(); i++) {
		swap(ans.at(i).at(0), ans.at(i).at(K));
	}
	if (!x) {
		stable_sort(ans.begin(), ans.end());
		reverse(ans.begin(), ans.end());
	}
	else {
		stable_sort(ans.begin(), ans.end());
	}

	for (ll i = 0; i < ans.size(); i++) {
		swap(ans.at(i).at(0), ans.at(i).at(K));
	}
	return ans;
}

void solve() {
	ll N, X, Y, Z; cin >> N >> X >> Y >> Z;
	vector<ll> A = import_vector(N);
	vector<ll> B = import_vector(N);

	vector<vector<ll>> score = {};
	for (ll i = 0; i < N; i++) {
		score.push_back({A.at(i), B.at(i), A.at(i) + B.at(i), i + 1});
	}

	map<ll, bool> passed = {};
	for (ll i = 1; i < N + 1; i++) {
		passed[i] = false;
	}

	vector<ll> ans = {};

	score = key_sort(score, 3, false);
	score = key_sort(score, 0, true);

	for (vector<ll> el: score) {
		show(el);
	}
	ll L1 = score.size();
	for (ll i = L1 - 1; i >= L1 - X; i--) {
		passed[score.at(i).at(3)] = true;
		ans.push_back(score.at(i).at(3));
	}

	vector<vector<ll>> score2 = {};
	for (ll i = 0; i < score.size(); i++) {
		if (passed[score.at(i).at(3)] == false) {
			score2.push_back(score.at(i));
		}
	}

	score2 = key_sort(score2, 3, false);
	score2 = key_sort(score2, 1, true);
	ll L2 = score2.size();
	for (ll i = L2 - 1; i >= L2 - Y; i--) {
		passed[score2.at(i).at(3)] = true;
		ans.push_back(score2.at(i).at(3));
	}

	vector<vector<ll>> score3 = {};
	for (ll i = 0; i < score2.size(); i++) {
		if (passed[score2.at(i).at(3)] == false) {
			score3.push_back(score2.at(i));
		}
	}

	score3 = key_sort(score3, 3, false);
	score3 = key_sort(score3, 2, true);
	ll L3 = score3.size();
	for (ll i = L3 - 1; i >= L3 - Z; i--) {
		ans.push_back(score3.at(i).at(3));
	}

	sort(ans.begin(), ans.end());
	for (ll el: ans) {
		cout << el << endl;
	}
}

int main() {
 solve();
}

Answer 1

以下のように修正すればコンパイルできます。
stable_sortの比較関数の引数は、Tかconst T&しか受け付けないようです。

stable_sort(score1.begin(), score1.end(), [] (const vector<ll> &alpha, const vector<ll> &beta) {return alpha[3] < beta[3];});
reverse(score1.begin(), score1.end());
stable_sort(score1.begin(), score1.end(), [] (const vector<ll> &alpha, const vector<ll> &beta) {return alpha[0] < beta[0];});

Comments

[kay_ventris4]

正解しました・・・！
ありがとうございます。そこにconst修飾子を付ければよかったんですね。勉強になりました。