Submission #2006350


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 = longestIncreasingSubsequence(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++14 (GCC 5.4.1)
Score 0
Code Size 5912 Byte
Status WA
Exec Time 2107 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 300
Status
WA × 3
TLE × 1
WA × 8
TLE × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt
Case Name Status Exec Time Memory
sample_01.txt WA 1 ms 256 KB
sample_02.txt WA 1 ms 256 KB
sample_03.txt WA 1 ms 256 KB
sample_04.txt TLE 2103 ms 256 KB
subtask_1_01.txt WA 1 ms 256 KB
subtask_1_02.txt TLE 2103 ms 256 KB
subtask_1_03.txt TLE 2103 ms 256 KB
subtask_1_04.txt TLE 2103 ms 256 KB
subtask_1_05.txt TLE 2103 ms 256 KB
subtask_1_06.txt TLE 2103 ms 256 KB
subtask_1_07.txt WA 280 ms 256 KB
subtask_1_08.txt TLE 2103 ms 256 KB
subtask_1_09.txt TLE 2103 ms 256 KB
subtask_1_10.txt TLE 2103 ms 256 KB
subtask_1_11.txt TLE 2107 ms 256 KB
subtask_1_12.txt TLE 2103 ms 256 KB
subtask_1_13.txt TLE 2103 ms 256 KB
subtask_1_14.txt TLE 2103 ms 256 KB
subtask_1_15.txt TLE 2103 ms 256 KB