#include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 1e6+100; ll l[maxn], a[maxn], b[maxn];; bool testCase(); int main(){ int T; cin >> T; while(T--){ if(testCase()) cout << "TAK" << endl; else cout << "NIE" << endl; } } bool testCase(){ int n; cin >> n; list <pll> g, w; for(int i = 0; i < n; i++){ ll a, b, c; cin >> a >> b >> c; g.pb(mp(b, a)); w.pb(mp(c, a)); } g.sort(); w.sort(); list <pll>::iterator git, wit; git = g.begin(); wit = w.begin(); list <pll>::iterator help; ll wsum = 0, gsum = 0; for(; git != g.end(); git++, wit++){ if(git->nd > wit->nd){ int r = git->nd - wit->nd; help = git; help++; g.insert(help, mp(git->st, r)); git->nd -= r; } else if(git->nd < wit->nd){ int r = wit->nd - git->nd; help = wit; help++; w.insert(help, mp(wit->st, r)); wit->nd -= r; } wsum += wit->st * wit->nd; gsum += git->st * git->nd; if(gsum - wsum > 0) return false; } if(gsum != wsum) return false; return true; }
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 | #include <bits/stdc++.h> #include <unordered_set> using namespace std; #define st first #define nd second #define pb push_back #define mp make_pair #define klar(v) memset(v, 0, sizeof(v)) #define bust ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define gcd(a, b) __gcd(a, b); #define debug(x) cout << #x << " " << x << endl; #define endl "\n" typedef vector<int> vi; typedef vector<pair<int, int> > vpii; typedef vector<long long> vll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef long long ll; const int maxn = 1e6+100; ll l[maxn], a[maxn], b[maxn];; bool testCase(); int main(){ int T; cin >> T; while(T--){ if(testCase()) cout << "TAK" << endl; else cout << "NIE" << endl; } } bool testCase(){ int n; cin >> n; list <pll> g, w; for(int i = 0; i < n; i++){ ll a, b, c; cin >> a >> b >> c; g.pb(mp(b, a)); w.pb(mp(c, a)); } g.sort(); w.sort(); list <pll>::iterator git, wit; git = g.begin(); wit = w.begin(); list <pll>::iterator help; ll wsum = 0, gsum = 0; for(; git != g.end(); git++, wit++){ if(git->nd > wit->nd){ int r = git->nd - wit->nd; help = git; help++; g.insert(help, mp(git->st, r)); git->nd -= r; } else if(git->nd < wit->nd){ int r = wit->nd - git->nd; help = wit; help++; w.insert(help, mp(wit->st, r)); wit->nd -= r; } wsum += wit->st * wit->nd; gsum += git->st * git->nd; if(gsum - wsum > 0) return false; } if(gsum != wsum) return false; return true; } |