#include <cstdio> #include <algorithm> #include <vector> #include <set> int cmpy(const std::pair<std::pair<int, int>, int > &lhs, const std::pair<std::pair<int, int>, int> &rhs) { if (lhs.first.second != rhs.first.second) return lhs.first.second < rhs.first.second; else return lhs.first.first < rhs.first.first; } long long int solve(const std::vector<std::pair<int, int> > point, int minx, int maxx, std::vector<int> &result) { std::set<std::pair<std::pair<int, int>, long long int> > used; //fromx,tox,toy int N = point.size(); for (int i=0; i<N; ++i) { if (point[i].first<minx || point[i].first>=maxx) return 0; int nextx = (((i+1<N) && (point[i+1].second==point[i].second))?point[i+1].first:maxx); std::set<std::pair<std::pair<int, int>, long long int> >::const_iterator ite, its, tmp; ite = its = used.lower_bound(std::make_pair(std::make_pair(point[i].first,-1),-1LL)); while (ite!=used.end() && ite->second<=point[i].second) { ite++; } if (its!=ite) { used.erase(its,ite); } if (ite!=used.end() && ite->first.first<nextx) { nextx=ite->first.first; } if (nextx==point[i].first) { return 0; } if (ite!=used.begin()) { tmp = its = ite; while (its!=used.begin() && (--tmp)->second<=point[i].second) { its--; } if (its!=ite) { used.erase(its,ite); } if (ite!=used.begin()) { ite--; if (ite->first.second>point[i].first) { return 0; } } } result[i] = nextx - point[i].first; used.insert(std::make_pair(std::make_pair(point[i].first,nextx), ((long long int)(point[i].second))+result[i])); } long long int field = 0; int miny = point[0].second; long long int maxy = 0; for (int i=0; i<N; ++i) { field += ((long long int)(result[i])) * result[i]; maxy = std::max(maxy, ((long long int)(point[i].second))+result[i]); } if (field == (((long long int)maxy)-miny)*(((long long int)maxx)-minx)) { return maxy-miny; } else { return 0; } } int main() { int T; scanf("%d",&T); while (T--) { int N; std::vector<std::pair<std::pair<int, int>, int> > pointm; std::vector<std::pair<int, int> > point; scanf("%d",&N); for (int i=0; i<N; ++i) { int x,y; scanf("%d %d",&x,&y); pointm.push_back(std::make_pair(std::make_pair(x,y), i)); } bool ok = false; std::vector<int> result(N,0); std::vector<int> fresult(N,0); if (N==1) { ok = true; fresult[0] = 1; } else { //sort points by y std::sort(pointm.begin(), pointm.end(), cmpy); for (int i=0; i<N; ++i) { point.push_back(pointm[i].first); } //find last point in deepest row int lpoint = 0; while (lpoint+1<N && point[lpoint+1].second==point[0].second) lpoint++; //try different sizes of lpoint int lasty = point[lpoint].second; for (int i=lpoint+1; !ok && i<N; ++i) { if (lasty != point[i].second) { long long int ret = solve(point, point[0].first, point[lpoint].first+point[i].second-point[lpoint].second, result); if (ret>0) { ok = true; for (int j=0; j<N; ++j) { fresult[pointm[j].second] = result[j]; } } } lasty = point[i].second; } //try without lpoint if (!ok) { int minx = point[0].first; int maxx = point[lpoint].first; long long int ret; point.erase(point.begin()+lpoint); ret = solve(point, minx, maxx, result); if (ret>0) { ok = true; for (int j=0; j<N; ++j) { if (j<lpoint) fresult[pointm[j].second] = result[j]; else if (j==lpoint) fresult[pointm[j].second] = ret; else fresult[pointm[j].second] = result[j-1]; } } } } if (ok) { printf("TAK "); for (int i=0; i<N; ++i) printf("%d ",fresult[i]); printf("\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 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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | #include <cstdio> #include <algorithm> #include <vector> #include <set> int cmpy(const std::pair<std::pair<int, int>, int > &lhs, const std::pair<std::pair<int, int>, int> &rhs) { if (lhs.first.second != rhs.first.second) return lhs.first.second < rhs.first.second; else return lhs.first.first < rhs.first.first; } long long int solve(const std::vector<std::pair<int, int> > point, int minx, int maxx, std::vector<int> &result) { std::set<std::pair<std::pair<int, int>, long long int> > used; //fromx,tox,toy int N = point.size(); for (int i=0; i<N; ++i) { if (point[i].first<minx || point[i].first>=maxx) return 0; int nextx = (((i+1<N) && (point[i+1].second==point[i].second))?point[i+1].first:maxx); std::set<std::pair<std::pair<int, int>, long long int> >::const_iterator ite, its, tmp; ite = its = used.lower_bound(std::make_pair(std::make_pair(point[i].first,-1),-1LL)); while (ite!=used.end() && ite->second<=point[i].second) { ite++; } if (its!=ite) { used.erase(its,ite); } if (ite!=used.end() && ite->first.first<nextx) { nextx=ite->first.first; } if (nextx==point[i].first) { return 0; } if (ite!=used.begin()) { tmp = its = ite; while (its!=used.begin() && (--tmp)->second<=point[i].second) { its--; } if (its!=ite) { used.erase(its,ite); } if (ite!=used.begin()) { ite--; if (ite->first.second>point[i].first) { return 0; } } } result[i] = nextx - point[i].first; used.insert(std::make_pair(std::make_pair(point[i].first,nextx), ((long long int)(point[i].second))+result[i])); } long long int field = 0; int miny = point[0].second; long long int maxy = 0; for (int i=0; i<N; ++i) { field += ((long long int)(result[i])) * result[i]; maxy = std::max(maxy, ((long long int)(point[i].second))+result[i]); } if (field == (((long long int)maxy)-miny)*(((long long int)maxx)-minx)) { return maxy-miny; } else { return 0; } } int main() { int T; scanf("%d",&T); while (T--) { int N; std::vector<std::pair<std::pair<int, int>, int> > pointm; std::vector<std::pair<int, int> > point; scanf("%d",&N); for (int i=0; i<N; ++i) { int x,y; scanf("%d %d",&x,&y); pointm.push_back(std::make_pair(std::make_pair(x,y), i)); } bool ok = false; std::vector<int> result(N,0); std::vector<int> fresult(N,0); if (N==1) { ok = true; fresult[0] = 1; } else { //sort points by y std::sort(pointm.begin(), pointm.end(), cmpy); for (int i=0; i<N; ++i) { point.push_back(pointm[i].first); } //find last point in deepest row int lpoint = 0; while (lpoint+1<N && point[lpoint+1].second==point[0].second) lpoint++; //try different sizes of lpoint int lasty = point[lpoint].second; for (int i=lpoint+1; !ok && i<N; ++i) { if (lasty != point[i].second) { long long int ret = solve(point, point[0].first, point[lpoint].first+point[i].second-point[lpoint].second, result); if (ret>0) { ok = true; for (int j=0; j<N; ++j) { fresult[pointm[j].second] = result[j]; } } } lasty = point[i].second; } //try without lpoint if (!ok) { int minx = point[0].first; int maxx = point[lpoint].first; long long int ret; point.erase(point.begin()+lpoint); ret = solve(point, minx, maxx, result); if (ret>0) { ok = true; for (int j=0; j<N; ++j) { if (j<lpoint) fresult[pointm[j].second] = result[j]; else if (j==lpoint) fresult[pointm[j].second] = ret; else fresult[pointm[j].second] = result[j-1]; } } } } if (ok) { printf("TAK "); for (int i=0; i<N; ++i) printf("%d ",fresult[i]); printf("\n"); } else { printf("NIE\n"); } } return 0; } |