#include #include #include using namespace std; struct student_t { int currSchool; int firstPreferred; int secondPreferred; }; int main() { ios_base::sync_with_stdio(0); cin.tie (0); int noStudents, noSchools, capacity; cin >> noStudents >> noSchools >> capacity; vector students (noStudents); vector> acceptedStudents (noSchools); for (int i = 0; i < noStudents; i++) { students[i].currSchool = -1; cin >> students[i].firstPreferred; cin >> students[i].secondPreferred; //Index from 0 students[i].firstPreferred--; students[i].secondPreferred--; } for (int i = 0; i < noSchools; i++) { acceptedStudents[i].clear (); } //First round for (int i = 0; i < noStudents; i++) { if (acceptedStudents[students[i].firstPreferred].size() < capacity) { students[i].currSchool = students[i].firstPreferred; acceptedStudents[students[i].firstPreferred].insert(i); } else if (acceptedStudents[students[i].secondPreferred].size() < capacity) { students[i].currSchool = students[i].secondPreferred; acceptedStudents[students[i].secondPreferred].insert(i); } } //Second round bool updateHappened = false; do { updateHappened = false; for (int school = 0; school < noSchools; school++) { for (int applicant = noStudents - 1; applicant >= 0; applicant--) { // Preskocit studenta, pokud uz je na skole if (students[applicant].currSchool != school) { continue; } // 2. podminka if (students[applicant].firstPreferred != school && students[applicant].secondPreferred != school) { continue; } // 3. podminka if (students[applicant].currSchool != -1 && students[applicant].currSchool != students[applicant].secondPreferred) { continue; } //1. podminka if (acceptedStudents[school].size() < capacity) { students[applicant].currSchool = school; acceptedStudents[school].insert(applicant); updateHappened = true; } else if (applicant < *(--acceptedStudents[school].end())) { acceptedStudents[students[applicant].currSchool].erase(applicant); students[applicant].currSchool = school; acceptedStudents[school].insert(applicant); updateHappened = true; } } } } while (updateHappened); int firstPriorityStudents = 0, secondPriorityStudents = 0; for (int i = 0; i < noStudents; i++) { if (students[i].currSchool == students[i].firstPreferred) { firstPriorityStudents++; } else if (students[i].currSchool == students[i].secondPreferred) { secondPriorityStudents++; } } cout << firstPriorityStudents << ' ' << secondPriorityStudents << endl; return 0; }