#include <iostream> #include<vector> #include<map> #include<algorithm> using namespace std; long long n; long long m; struct paper { int i; map<int, int> modifications; }; void newPaper(paper& old, paper& toFill, int* p, int pi, int x) { int d = x - p[pi]; for(const auto& kv: old.modifications) { toFill.modifications[kv.first] = kv.second; } if(d == 0) { toFill.modifications.erase(pi); } else { toFill.modifications[pi] = d; } } bool cmpPapers(const paper &a, const paper &b) { //a < b; bool r = true; map<int,int>::const_iterator ai = a.modifications.begin(); map<int,int>::const_iterator bi = b.modifications.begin(); while(ai != a.modifications.end() && bi != b.modifications.end()) { if (ai->first < bi->first) { return ai->second < 0; } else if(ai->first > bi->first) { return 0 < bi->second; } else { int av = ai->second; int bv = bi->second; if (av != bv) { return av < bv; } } ai++; bi++; } if(ai != a.modifications.end()) { return ai->second < 0; }; if(bi != b.modifications.end()) { return 0 < bi->second; } return false; //equal; } int main(int argc, const char* argv[]) { cin >> n; cin >> m; int p[n]; for(int i = 0; i < n; i++) { cin >> p[i]; } vector<paper> papers (m); papers[0].i = 1; int pi, x; for(int i = 1; i < m; i++) { cin >> pi; pi--; cin >> x; papers[i].i = i+1; newPaper(papers[i-1], papers[i], p, pi, x); } sort(papers.begin(), papers.end(), cmpPapers); for(int i = 0; i < m; i++) { cout << papers[i].i << " "; } cout << 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 76 77 78 79 80 81 82 83 84 85 86 87 | #include <iostream> #include<vector> #include<map> #include<algorithm> using namespace std; long long n; long long m; struct paper { int i; map<int, int> modifications; }; void newPaper(paper& old, paper& toFill, int* p, int pi, int x) { int d = x - p[pi]; for(const auto& kv: old.modifications) { toFill.modifications[kv.first] = kv.second; } if(d == 0) { toFill.modifications.erase(pi); } else { toFill.modifications[pi] = d; } } bool cmpPapers(const paper &a, const paper &b) { //a < b; bool r = true; map<int,int>::const_iterator ai = a.modifications.begin(); map<int,int>::const_iterator bi = b.modifications.begin(); while(ai != a.modifications.end() && bi != b.modifications.end()) { if (ai->first < bi->first) { return ai->second < 0; } else if(ai->first > bi->first) { return 0 < bi->second; } else { int av = ai->second; int bv = bi->second; if (av != bv) { return av < bv; } } ai++; bi++; } if(ai != a.modifications.end()) { return ai->second < 0; }; if(bi != b.modifications.end()) { return 0 < bi->second; } return false; //equal; } int main(int argc, const char* argv[]) { cin >> n; cin >> m; int p[n]; for(int i = 0; i < n; i++) { cin >> p[i]; } vector<paper> papers (m); papers[0].i = 1; int pi, x; for(int i = 1; i < m; i++) { cin >> pi; pi--; cin >> x; papers[i].i = i+1; newPaper(papers[i-1], papers[i], p, pi, x); } sort(papers.begin(), papers.end(), cmpPapers); for(int i = 0; i < m; i++) { cout << papers[i].i << " "; } cout << endl; return 0; } |