Hướng dẫn giải của C3
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Chia kì thủ thành 4 nhóm theo giới tính và tuổi. Nhóm nam-trẻ đấu với nữ-trẻ, nam-già đấu với nữ-già. Với mỗi truy vấn, đếm số đối thủ trong nhóm đối nghịch có elo nhỏ hơn elo của kì thủ được hỏi.
Sub 1: vét cạn — ~O(n \cdot T)~, dùng khi ~n \cdot T \le 10^7~
Với mỗi truy vấn, duyệt hết kì thủ và đếm. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: sắp xếp elo theo nhóm — ~O((n+T) \log n)~
Lưu elo của từng nhóm đã sắp xếp. Mỗi truy vấn dùng lower_bound để đếm số elo nhỏ hơn. Đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu và xếp nhóm cho từng kì thủ. Nếu ~n \cdot T \le 10^7~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, T;
vector<int> B, C, D; // giới tính (1 nam, 0 nữ), tuổi, elo của kì thủ có số báo danh i
vector<int> grp; // nhóm: 0 nam-trẻ, 1 nam-già, 2 nữ-trẻ, 3 nữ-già
// Nhóm đối thủ của nhóm g: nam-trẻ (0) với nữ-trẻ (2), nam-già (1) với nữ-già (3)
int oppositeGroup(int g) { return g ^ 2; }
// Sub 1: với mỗi truy vấn, duyệt toàn bộ kì thủ. O(n*T). Dùng khi n*T nhỏ.
void sub1(const vector<int> &qs) {
for (int x : qs) {
int cnt = 0;
for (int i = 1; i <= n; i++)
if (grp[i] == oppositeGroup(grp[x]) && D[i] < D[x]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sắp xếp elo của từng nhóm, mỗi truy vấn dùng lower_bound. O(n log n + T log n)
void sub2(const vector<int> &qs) {
vector<int> elo[4];
for (int i = 1; i <= n; i++) elo[grp[i]].push_back(D[i]);
for (int g = 0; g < 4; g++) sort(elo[g].begin(), elo[g].end());
for (int x : qs) {
const vector<int> &v = elo[oppositeGroup(grp[x])];
int cnt = lower_bound(v.begin(), v.end(), D[x]) - v.begin(); // số elo < elo của x
cout << cnt << "\n";
}
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> T;
B.assign(n + 1, 0); C.assign(n + 1, 0); D.assign(n + 1, 0); grp.assign(n + 1, 0);
for (int i = 0; i < n; i++) {
int A, b, c, d;
cin >> A >> b >> c >> d;
B[A] = b; C[A] = c; D[A] = d;
grp[A] = (b == 1 ? 0 : 2) + (c >= 50 ? 1 : 0);
}
vector<int> qs(T);
for (int t = 0; t < T; t++) cin >> qs[t];
if ((long long)n * T <= 10000000LL) sub1(qs);
else sub2(qs);
return 0;
}
Bình luận