#include <cstdio> #include <algorithm> #include <vector> using namespace std; #define forv(na,it) for(__typeof(na.begin()) it=na.begin(); it!=na.end(); it++) struct zadania { int x, p, k; }p[102]; bool operator < (zadania a, zadania b) { return a.p<b.p; } struct wp { int ro, k, zos; }; bool operator < (wp a, wp b) { if (a.ro!=b.ro) return a.ro<b.ro; return a.k>b.k; } wp make_wp (int ro, int k, int zos) { wp pom; pom.ro=ro; pom.k=k; pom.zos=zos; return pom; } int main () { vector <wp> v; int n, k, mx=0, suma=0; scanf ("%d%d", &n, &k); for (int i=0; i<n; i++) { scanf ("%d%d%d", &p[i].p, &p[i].k, &p[i].x); mx=max(mx, p[i].k); suma+=p[i].x; } if (k>=n) { printf ("TAK"); return 0; } sort (p, p+n); if ((mx-p[0].p)*k<suma) { printf ("NIE"); return 0; } int wskbierz=0, dl, pocz, kon; //printf ("brut\n"); for (int i=p[0].p; i<=mx; i++) { //printf ("sekund : %d ", i); if (!v.empty()) for (int j=0; j<v.size();) { if (v[j].zos<=0) { v.erase(v.begin()+j); } else if (v[j].k==i) { printf ("NIE"); return 0; } else j++; } while (wskbierz<n && p[wskbierz].p==i) { v.push_back(make_wp(p[wskbierz].k-p[wskbierz].p-p[wskbierz].x, p[wskbierz].k, p[wskbierz].x)); wskbierz++; sort (v.begin(), v.end()); } //forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n"); dl=min(k, (int)v.size()); for (int j=0; j<dl; j++) v[j].zos--; if (k<v.size()) for (int j=k; j<v.size(); j++) { v[j].ro--; if (v[j].ro<0) { printf ("NIE"); return 0; } } //printf ("przed : "); forv(v, it) printf ("%d ", it->ro); printf ("\n"); //sort (v.begin(), v.end()); if (k<v.size()) { for (kon=k; kon<v.size();kon++) if (v[k-1].ro<=v[kon].ro) break; for (pocz=k-1; pocz>=0;pocz--) if (v[pocz].ro<=v[k].ro) break; kon--; pocz++; reverse (v.begin()+pocz, v.begin()+k); reverse (v.begin()+k, v.begin()+kon+1); reverse (v.begin()+pocz, v.begin()+kon+1); } //printf ("po : "); forv(v, it) printf ("%d ", it->ro); printf ("\n"); //forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n"); //forv(v, it) printf ("%d ", it->k); } printf ("TAK"); 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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <cstdio> #include <algorithm> #include <vector> using namespace std; #define forv(na,it) for(__typeof(na.begin()) it=na.begin(); it!=na.end(); it++) struct zadania { int x, p, k; }p[102]; bool operator < (zadania a, zadania b) { return a.p<b.p; } struct wp { int ro, k, zos; }; bool operator < (wp a, wp b) { if (a.ro!=b.ro) return a.ro<b.ro; return a.k>b.k; } wp make_wp (int ro, int k, int zos) { wp pom; pom.ro=ro; pom.k=k; pom.zos=zos; return pom; } int main () { vector <wp> v; int n, k, mx=0, suma=0; scanf ("%d%d", &n, &k); for (int i=0; i<n; i++) { scanf ("%d%d%d", &p[i].p, &p[i].k, &p[i].x); mx=max(mx, p[i].k); suma+=p[i].x; } if (k>=n) { printf ("TAK"); return 0; } sort (p, p+n); if ((mx-p[0].p)*k<suma) { printf ("NIE"); return 0; } int wskbierz=0, dl, pocz, kon; //printf ("brut\n"); for (int i=p[0].p; i<=mx; i++) { //printf ("sekund : %d ", i); if (!v.empty()) for (int j=0; j<v.size();) { if (v[j].zos<=0) { v.erase(v.begin()+j); } else if (v[j].k==i) { printf ("NIE"); return 0; } else j++; } while (wskbierz<n && p[wskbierz].p==i) { v.push_back(make_wp(p[wskbierz].k-p[wskbierz].p-p[wskbierz].x, p[wskbierz].k, p[wskbierz].x)); wskbierz++; sort (v.begin(), v.end()); } //forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n"); dl=min(k, (int)v.size()); for (int j=0; j<dl; j++) v[j].zos--; if (k<v.size()) for (int j=k; j<v.size(); j++) { v[j].ro--; if (v[j].ro<0) { printf ("NIE"); return 0; } } //printf ("przed : "); forv(v, it) printf ("%d ", it->ro); printf ("\n"); //sort (v.begin(), v.end()); if (k<v.size()) { for (kon=k; kon<v.size();kon++) if (v[k-1].ro<=v[kon].ro) break; for (pocz=k-1; pocz>=0;pocz--) if (v[pocz].ro<=v[k].ro) break; kon--; pocz++; reverse (v.begin()+pocz, v.begin()+k); reverse (v.begin()+k, v.begin()+kon+1); reverse (v.begin()+pocz, v.begin()+kon+1); } //printf ("po : "); forv(v, it) printf ("%d ", it->ro); printf ("\n"); //forv(v, it) printf ("{%d %d %d} ", it->ro, it->k, it->zos); printf ("\n"); //forv(v, it) printf ("%d ", it->k); } printf ("TAK"); return 0; } |