Submission #2006159
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct Point { int x; int y; }; bool compareOnX(Point f1, Point f2) { return f1.x < f2.x; } // Binary search for largest index j in array v // so that v[j] < number. int binarySearch(const vector<int>& v, int lo, int hi, int number) { while (hi > lo + 1) { int mid = lo + (hi - lo) / 2; if (v[mid] >= number) { hi = mid; } else { lo = mid; } } if (v[hi] < number) { return hi; } else if (v[lo] < number) { return lo; } else { return -1; } } // O(N * log(K)) solution int longestIncreasingSubsequenceEfficient(const vector<int>& a) { vector<int> dp(a.size(), 0); if (a.size() == 0) return 0; dp[0] = 1; // Length of LIS ending on first element is 1. vector<int> smallest_last_element_for_length(a.size(), 0); smallest_last_element_for_length[0] = a[0]; // Careful: element with index 0 is for length 1. int k = 1; // Length of longest increasing subsequence seen so far. // Loop over subproblems. for (int i = 1; i < a.size(); ++i) { // Binary search for largest index j in smallest_last_element_for_length // so that smallest_last_element_for_length[j] < a[i]. int lo = 0; int hi = min(i - 1, k - 1); // hi cannot be larger than largest length so far. int max_len = binarySearch(smallest_last_element_for_length, lo, hi, a[i]) + 1; dp[i] = 1 + max_len; if (dp[i] > k) { // If larger LIS length than what we've seen uptil now. // Update state variables. k = dp[i]; smallest_last_element_for_length[k - 1] = a[i]; } else { if (a[i] < smallest_last_element_for_length[dp[i] - 1]) { smallest_last_element_for_length[dp[i] - 1] = a[i]; } } } return k; } // O(N^2) solution int longestIncreasingSubsequence(vector<int> a) { vector<int> dp(a.size(), 0); if (a.size() == 0) return 0; dp[0] = 1; // length of LIS ending on first element is 1. for (int i = 1; i < a.size(); ++i) { // Max over LIS lengths where last element smaller than a[i]. int mx = 0; for (int j = 0; j < i; ++j) { if (dp[j] > mx && a[j] < a[i]) { mx = dp[j]; } } dp[i] = 1 + mx; } // Max of all LIS lengths. int ans = 0; for (int i = 0; i < dp.size(); ++i) { if (dp[i] > ans) { ans = dp[i]; } } return ans; } double pathLength(Point p1, Point p2, int number_of_fountains) { // Also include scenario where number_of_fountains == 0. // Also include scenario where start and stop have same x or y value. double manhattan_path_length = 100 * ((p2.x - p1.x) + (p2.y - p1.y)); double radius = 10; double quarter_circumference = M_PI * radius / 2; if ((p1.x == p2.x) || (p1.y == p2.y)) { if (number_of_fountains == 0) { return manhattan_path_length; } else if (number_of_fountains == 1) { return manhattan_path_length - 2 * radius + 2 * quarter_circumference; } else { cout << "Error. This should never happen." << endl; return -1; } } else { return manhattan_path_length - number_of_fountains * (2 * radius - quarter_circumference); } } void solve() { int x1, y1, x2, y2, N; cin >> x1 >> y1 >> x2 >> y2; cin >> N; // Make start the leftmost point of the two. Point start = {x1, y1}; Point stop = {x2, y2}; if (start.x > stop.x) { Point tmp = start; start = stop; stop = tmp; } // If start above stop, flip around x axis. bool flip_around_x_axis = false; if (start.y > stop.y) { flip_around_x_axis = true; start.y = - start.y; stop.y = - stop.y; } vector<Point> fountains; // Add fountains if within rectangle. for (int i = 0; i < N; ++i) { int x, y; cin >> x >> y; if (flip_around_x_axis) { y = - y; } if (x >= start.x && x <= stop.x && y >= start.y && y <= stop.y) { fountains.push_back({x, y}); } } // Sort fountains along x. sort(fountains.begin(), fountains.end(), compareOnX); // Find number of fountains on optimal path. vector<int> y_coords; y_coords.reserve(fountains.size()); for (int i = 0; i < fountains.size(); ++i) { y_coords.push_back(fountains[i].y); } int number_of_fountains = longestIncreasingSubsequenceEfficient(y_coords); // Calculate path length from number_of_fountains. double path_length = pathLength(start, stop, number_of_fountains); cout.precision(18); cout << path_length << endl; } void testlongestIncreasingSubsequenceEfficient() { vector<int> array1 = {1, 2, 3, 4, 5}; assert(longestIncreasingSubsequenceEfficient(array1) == 5); vector<int> array2 = {-1, 4, -3, 5, 6}; assert(longestIncreasingSubsequenceEfficient(array2) == 4); vector<int> array3 = {0, 10, 2, 3, 4, 22, 6, -8, -7, -6, -5, -4}; assert(longestIncreasingSubsequenceEfficient(array3) == 5); vector<int> array4 = {10, 2, 3, 4, 5}; assert(longestIncreasingSubsequenceEfficient(array4) == 4); vector<int> array5(200000); for (int i = 0; i < array5.size(); ++i) { array5[i] = i; } assert(longestIncreasingSubsequenceEfficient(array5) == array5.size()); } int main() { // freopen("/Users/simon/Downloads/test.in", "r", stdin); // testlongestIncreasingSubsequenceEfficient(); // freopen("/Users/simon/Downloads/test.out", "w", stdout); solve(); }
Submission Info
Submission Time | |
---|---|
Task | A - Ice Tea Store |
User | quinoa |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 5921 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void solve()’: ./Main.cpp:137:33: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 fountains.push_back({x, y}); ^ ./Main.cpp:137:39: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 fountains.push_back({x, y}); ^ ./Main.cpp: In function ‘void testlongestIncreasingSubsequenceEfficient()’: ./Main.cpp:156:40: error: in C++98 ‘array1’ must be initialized by constructor, not by ‘{...}’ vector<int> array1 = {1, 2, 3, 4, 5}; ^ ./Main.cpp:156:40: error: could not convert ‘{1, 2, 3, 4, 5}’ from ‘<brace-enclosed initializer list>’ to ‘std::vector<int>’ ./Main.cpp:158:42: error: in C++98 ‘array2’ must be initialized by constructor, not by ‘{...}’ vector<int> array2 = {-1, 4, -3, 5, 6}; ^ ./Main.cpp:158:42: error: could not convert ‘{-1, 4...