// 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; } |