#include <cstdio> #include <vector> #include <utility> #include <algorithm> using namespace std; typedef pair<pair<int,int>,int> smok; vector<smok> dod, uje; vector<int> wyn; bool newsort (smok a,smok b) {return (a.first.second+a.first.first>b.first.second+b.first.first);} int main() { int n, hpreq, hppack, bilans, hp0; long long int hp; scanf("%d %d", &n, &hp0); hp=hp0; for(int i=0; i<n; i++) { scanf("%d %d", &hpreq, &hppack); bilans=hppack-hpreq; if(bilans>=0) dod.push_back(make_pair(make_pair(hpreq, bilans), i+1)); else uje.push_back(make_pair(make_pair(hpreq, bilans), i+1)); } sort(dod.begin(), dod.end()); for(int i=0; i<dod.size(); i++) { hp-=dod[i].first.first; if(hp<=0) {printf("NIE"); return 0;} hp+=dod[i].first.second+dod[i].first.first; wyn.push_back(dod[i].second); } sort(uje.begin(), uje.end(), newsort); for(int i=0; i<uje.size(); i++) { hp-=uje[i].first.first; if(hp<=0) {printf("NIE"); return 0;} hp+=uje[i].first.second+uje[i].first.first; wyn.push_back(uje[i].second); } printf("TAK\n"); for(int i=0; i<wyn.size(); i++) printf("%d ", wyn[i]); 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 | #include <cstdio> #include <vector> #include <utility> #include <algorithm> using namespace std; typedef pair<pair<int,int>,int> smok; vector<smok> dod, uje; vector<int> wyn; bool newsort (smok a,smok b) {return (a.first.second+a.first.first>b.first.second+b.first.first);} int main() { int n, hpreq, hppack, bilans, hp0; long long int hp; scanf("%d %d", &n, &hp0); hp=hp0; for(int i=0; i<n; i++) { scanf("%d %d", &hpreq, &hppack); bilans=hppack-hpreq; if(bilans>=0) dod.push_back(make_pair(make_pair(hpreq, bilans), i+1)); else uje.push_back(make_pair(make_pair(hpreq, bilans), i+1)); } sort(dod.begin(), dod.end()); for(int i=0; i<dod.size(); i++) { hp-=dod[i].first.first; if(hp<=0) {printf("NIE"); return 0;} hp+=dod[i].first.second+dod[i].first.first; wyn.push_back(dod[i].second); } sort(uje.begin(), uje.end(), newsort); for(int i=0; i<uje.size(); i++) { hp-=uje[i].first.first; if(hp<=0) {printf("NIE"); return 0;} hp+=uje[i].first.second+uje[i].first.first; wyn.push_back(uje[i].second); } printf("TAK\n"); for(int i=0; i<wyn.size(); i++) printf("%d ", wyn[i]); return 0; } |