#include <iostream> #include <assert.h> #include <algorithm> #include <list> #include <numeric> #include <array> #include <functional> #include <queue> using namespace std; #define MAXN 50000 int n = 5, m = 8; typedef array<int, MAXN> Temperature; #define EXIT_GRACEFULLY return 0;//delete[] alina; struct Change { int p, x; }; struct Student { int index; Change temperature; }; function<Temperature(Change)> generateTemperature(Temperature first) { return [first](Change change) mutable -> Temperature { first[change.p-1] = change.x; return first; }; } vector<Change> changes; Change getChange(int index) { return changes[index-2]; } Temperature temperatureFor(Temperature first, int index) { int i = 2; if(index == 1) { return first; } auto generator = generateTemperature(first); Temperature temperature; do { temperature = generator(getChange(i)); }while(i++ != index); return temperature; } class CompareStudents { Temperature alina; public: CompareStudents(Temperature alina) { this->alina = alina; } bool operator() (const Student &lhs, const Student &rhs) { Temperature lTemp = temperatureFor(alina, lhs.index); // cout << "hello " << rhs.index << " " << rhs.temperature.p << " " << rhs.temperature.x << endl; Temperature rTemp = temperatureFor(alina, rhs.index); // assert(lTemp.size() == rTemp.size()); // for (int i = 0; i < lTemp.size(); ++i) { for (int i = 0; i < n; ++i) { if(lTemp[i] < rTemp[i]) return false; if(lTemp[i] > rTemp[i]) return true; } return lhs.index > rhs.index; } }; int main() { ios_base::sync_with_stdio(false); Temperature alina; /* for (int j = 0; j < n; ++j) { cout << alina[j] << endl; }*/ cin >> n >> m; if(n > MAXN) return 62; for (int j = 0; j < n; ++j) { // int t; // cin >> t; // alina.push_back(t); cin >> alina[j]; } typedef priority_queue<Student, vector<Student>, CompareStudents> stQueue; CompareStudents compareStudents(alina); stQueue students(compareStudents); students.push(Student{1, {0, 0}}); Temperature currentTemperature; for (int i = 2; i <= m; ++i) { int p, x; cin >> p >> x; Change change {p, x}; changes.push_back(change); Student current {i, change}; auto temperatureGenerator = generateTemperature(alina); auto temp = temperatureGenerator(change); /*for (int j = 0; j < n; ++j) { cout << temp[j] << endl; }*/ students.push(current); } while(!students.empty()) { cout << students.top().index << " "; students.pop(); } cout << endl; EXIT_GRACEFULLY }
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #include <iostream> #include <assert.h> #include <algorithm> #include <list> #include <numeric> #include <array> #include <functional> #include <queue> using namespace std; #define MAXN 50000 int n = 5, m = 8; typedef array<int, MAXN> Temperature; #define EXIT_GRACEFULLY return 0;//delete[] alina; struct Change { int p, x; }; struct Student { int index; Change temperature; }; function<Temperature(Change)> generateTemperature(Temperature first) { return [first](Change change) mutable -> Temperature { first[change.p-1] = change.x; return first; }; } vector<Change> changes; Change getChange(int index) { return changes[index-2]; } Temperature temperatureFor(Temperature first, int index) { int i = 2; if(index == 1) { return first; } auto generator = generateTemperature(first); Temperature temperature; do { temperature = generator(getChange(i)); }while(i++ != index); return temperature; } class CompareStudents { Temperature alina; public: CompareStudents(Temperature alina) { this->alina = alina; } bool operator() (const Student &lhs, const Student &rhs) { Temperature lTemp = temperatureFor(alina, lhs.index); // cout << "hello " << rhs.index << " " << rhs.temperature.p << " " << rhs.temperature.x << endl; Temperature rTemp = temperatureFor(alina, rhs.index); // assert(lTemp.size() == rTemp.size()); // for (int i = 0; i < lTemp.size(); ++i) { for (int i = 0; i < n; ++i) { if(lTemp[i] < rTemp[i]) return false; if(lTemp[i] > rTemp[i]) return true; } return lhs.index > rhs.index; } }; int main() { ios_base::sync_with_stdio(false); Temperature alina; /* for (int j = 0; j < n; ++j) { cout << alina[j] << endl; }*/ cin >> n >> m; if(n > MAXN) return 62; for (int j = 0; j < n; ++j) { // int t; // cin >> t; // alina.push_back(t); cin >> alina[j]; } typedef priority_queue<Student, vector<Student>, CompareStudents> stQueue; CompareStudents compareStudents(alina); stQueue students(compareStudents); students.push(Student{1, {0, 0}}); Temperature currentTemperature; for (int i = 2; i <= m; ++i) { int p, x; cin >> p >> x; Change change {p, x}; changes.push_back(change); Student current {i, change}; auto temperatureGenerator = generateTemperature(alina); auto temp = temperatureGenerator(change); /*for (int j = 0; j < n; ++j) { cout << temp[j] << endl; }*/ students.push(current); } while(!students.empty()) { cout << students.top().index << " "; students.pop(); } cout << endl; EXIT_GRACEFULLY } |