// Task: SAM
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<vector<int>> characteristics(2);
for (auto v: characteristics) {
v.reserve(n);
}
for (int i = 0; i < n; ++i) {
int r, w, t;
cin >> r >> w >> t;
characteristics[r - 1].push_back(w - t);
}
for (int i = 0; i < characteristics.size(); ++i) {
sort(characteristics[i].begin(), characteristics[i].end());
}
int toRemove = 0;
vector<int>::iterator iterators[2];
for (int i = 0; i < 2; ++i) {
iterators[i] = characteristics[i].begin();
}
// Illustration
// 1 1 2 3 3 3 4 5 6
// 2 2 2 2 3 3 5 7 7
while (iterators[0] != characteristics[0].end() &&
iterators[1] != characteristics[1].end()) {
if (*iterators[0] < *iterators[1]){
++iterators[0];
continue;
}
if (*iterators[0] > *iterators[1]){
++iterators[1];
continue;
}
const int COMMON_VALUE = *iterators[0];
int collisions[2] = {0, 0};
for (int i = 0; i < 2; ++i) {
while ((iterators[i] != characteristics[i].end()) &&
*iterators[i] == COMMON_VALUE){
++collisions[i];
++iterators[i];
}
}
toRemove += min(collisions[0], collisions[1]);
}
cout << toRemove << endl;
return 0;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | // Task: SAM #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n; cin >> n; vector<vector<int>> characteristics(2); for (auto v: characteristics) { v.reserve(n); } for (int i = 0; i < n; ++i) { int r, w, t; cin >> r >> w >> t; characteristics[r - 1].push_back(w - t); } for (int i = 0; i < characteristics.size(); ++i) { sort(characteristics[i].begin(), characteristics[i].end()); } int toRemove = 0; vector<int>::iterator iterators[2]; for (int i = 0; i < 2; ++i) { iterators[i] = characteristics[i].begin(); } // Illustration // 1 1 2 3 3 3 4 5 6 // 2 2 2 2 3 3 5 7 7 while (iterators[0] != characteristics[0].end() && iterators[1] != characteristics[1].end()) { if (*iterators[0] < *iterators[1]){ ++iterators[0]; continue; } if (*iterators[0] > *iterators[1]){ ++iterators[1]; continue; } const int COMMON_VALUE = *iterators[0]; int collisions[2] = {0, 0}; for (int i = 0; i < 2; ++i) { while ((iterators[i] != characteristics[i].end()) && *iterators[i] == COMMON_VALUE){ ++collisions[i]; ++iterators[i]; } } toRemove += min(collisions[0], collisions[1]); } cout << toRemove << endl; return 0; } |
English