/* Topcoder SRM 699, D2, 500-pointer: SegmentsAndPoints. James S. Plank October 9, 2016 */ #include #include #include #include #include #include #include #include #include #include using namespace std; class SegmentsAndPoints { public: string isPossible(vector p, vector l, vector r); }; string SegmentsAndPoints::isPossible(vector p, vector l, vector r) { int i, j, best_segment; vector done; /* Start by sorting p, and setting all of the "done" entries to zero. */ sort(p.begin(), p.end()); done.resize(p.size(), 0); /* Now, for each point in p, find the segment that is not done, contains the point, and has the smallest r value. Put that into "best_segment" */ for (i = 0; i < p.size(); i++) { best_segment = -1; for (j = 0; j < p.size(); j++) { if (!done[j] && l[j] <= p[i] && r[j] >= p[i]) { if (best_segment == -1 || r[j] < r[best_segment]) best_segment = j; } } /* If there is such segment, return "Impossible. Otherwise, set the segment's "done" value to 1. */ if (best_segment == -1) return "Impossible"; done[best_segment] = 1; } /* If we've reached the end, return "Possible" */ return "Possible"; }