#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; int t; int main() { // your code goes here scanf("%d",&t); while(t--) { long long n; map<long long, long long> a; map<long long, long long> b; scanf("%lld",&n); for(int i =0;i<n;i++) { long long l,ai,bi; scanf("%lld%lld%lld",&l,&ai,&bi); a[ai]+=l; b[bi]+=l; } /* printf("\ntest %u: n=%llu\na: ",t,n); for_each(a.begin(), a.end(), [](auto it) { printf("<%llu %llu>, ",it.first, it.second); }); printf("\nb: "); for_each(b.begin(), b.end(), [](auto it) { printf("<%llu %llu>, ",it.first, it.second); }); printf("\n\n"); for(auto rit = a.rbegin(); rit!=a.rend(); rit++) { printf("<%llu %llu>, ",rit->first, rit->second); } */ long long area = 0; while(!a.empty() && !b.empty()) { auto arit = a.rbegin(); auto brit = b.rbegin(); auto ai = arit->first; auto la = arit->second; auto bi = brit->first; auto lb = brit->second; //printf("a=%lld,%lld b=%lld,%lld area:%lld ai-bi=%lld\n",ai,la,bi,lb,area,ai-bi); //a.erase(make_pair(ai,la)); //b.erase(make_pair(bi,lb)); if(la > lb) { a[ai]-=lb; b.erase(bi); area += lb*(ai-bi); } else if(la < lb) { b[bi]-=la; a.erase(ai); area += la*(ai-bi); } else { a.erase(ai); b.erase(bi); area += la*(ai-bi); } if (area<0) { a.clear(); b.clear(); } //printf("a=%lld,%lld b=%lld,%lld area:%lld\n",ai,la,bi,lb,area); } if(area == 0) printf("TAK\n"); else printf("NIE\n"); } 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 | #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; int t; int main() { // your code goes here scanf("%d",&t); while(t--) { long long n; map<long long, long long> a; map<long long, long long> b; scanf("%lld",&n); for(int i =0;i<n;i++) { long long l,ai,bi; scanf("%lld%lld%lld",&l,&ai,&bi); a[ai]+=l; b[bi]+=l; } /* printf("\ntest %u: n=%llu\na: ",t,n); for_each(a.begin(), a.end(), [](auto it) { printf("<%llu %llu>, ",it.first, it.second); }); printf("\nb: "); for_each(b.begin(), b.end(), [](auto it) { printf("<%llu %llu>, ",it.first, it.second); }); printf("\n\n"); for(auto rit = a.rbegin(); rit!=a.rend(); rit++) { printf("<%llu %llu>, ",rit->first, rit->second); } */ long long area = 0; while(!a.empty() && !b.empty()) { auto arit = a.rbegin(); auto brit = b.rbegin(); auto ai = arit->first; auto la = arit->second; auto bi = brit->first; auto lb = brit->second; //printf("a=%lld,%lld b=%lld,%lld area:%lld ai-bi=%lld\n",ai,la,bi,lb,area,ai-bi); //a.erase(make_pair(ai,la)); //b.erase(make_pair(bi,lb)); if(la > lb) { a[ai]-=lb; b.erase(bi); area += lb*(ai-bi); } else if(la < lb) { b[bi]-=la; a.erase(ai); area += la*(ai-bi); } else { a.erase(ai); b.erase(bi); area += la*(ai-bi); } if (area<0) { a.clear(); b.clear(); } //printf("a=%lld,%lld b=%lld,%lld area:%lld\n",ai,la,bi,lb,area); } if(area == 0) printf("TAK\n"); else printf("NIE\n"); } return 0; } |