Some thing wrong with OJ on the large test case


  • 0
    P

    The below code runs fine on my machine but gives TLE on OJ
    #include <iostream>
    #include <vector>
    #include <limits.h>

    using namespace std;
    
    int jump(vector<int> a, int n) {
            if (n==1) return 0;
            if (a[0] >= n-1) {
                cout << "returning from here\n";
                return 1;
            }
            vector<int> reach(n,INT_MAX);
            reach[0] = 0;
            int tot_int_max = n-1;
            long count_inner = 0;
            for (int i = 0; i < n && tot_int_max > 0; ++i) {
                int j = a[i]+i < n ? a[i] : n-i-1;
                while(j > 0) {
                    count_inner++;
                    tot_int_max = reach[i+j] == INT_MAX ? tot_int_max-1 : tot_int_max;
                    reach[i+j] = min(reach[i+j], i);
                    j--;
                    if (tot_int_max==0) break;
                }
            }
            
            int steps = 0;
            int i = n-1;
            while(i > 0) {
                cout << "here\n";
                steps++;
                i = reach[i];
            } 
    
            cout << "innner loop " << count_inner << "\n";
            return steps;
    }
    
    int main() {
    vector<int> a;
    for (int i = 25000; i >= 23697; --i) {
    a.push_back(i);
    }
    a.push_back(23);
    cout << jump(a,a.size()) << "\n";
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.