My account have been banned for the Weekly Contest 187
ywl
1609

@LeetCode hello, leetcode, it seems that my account [WanGong] has been bannd. The system think I have a plagiarize in the contest Weekly Contest 187, but I DID NOT do that. I finish the contest by myself, NEVER copy other's solution and NEVER share my solution to others. I think it should be a FP, below is my submits, could you help to check it?

Q1:

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        map<string, int> data;
        for (const auto& p : paths) {
            data[p[0]] = 1;
            data[p[1]] = data[p[1]];
        }
        
        for (const auto& p : data) {
            if (p.second == 0) {
                return p.first;
            }
        }
        
        return "";
    }
};

Q2:

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int last = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1) {
                if (last == -1) {
                    last = i;
                } else {
                    if (i - last - 1 < k) {
                        return false;
                    }
                    last = i;
                }
            }
        }
        
        return true;
    }
};

Q3:

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int last = 0;
        int res = 0;
        multiset<int> s;
        
        for (int i = 0; i < nums.size(); ++i) {
            s.insert(nums[i]);
            while (*s.rbegin() - *s.begin() > limit) {
                s.erase(nums[last++]);
            }
            res = max<int>(res, s.size());
        }
        
        return res;
    }
};

Q4:
1st submit [timeout]:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        long long l = 0, r = 0;
        for (const auto& m : mat) {
            l += m.front();
            r += m.back();
        }
        
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long n = count(mat, 0, mid);
            cout << mid << ": " << n << endl;
            if (n >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    long long count(vector<vector<int>>& mat, int pos, int val) {
        if (pos >= mat.size()) {
            return 1;
        }
        
        long long res = 0;
        for (int i = 0; i < mat[pos].size(); ++i) {
            if (mat[pos][i] <= val) {
                res += count(mat, pos + 1, val - mat[pos][i]);
            } else {
                break;
            }
        }
        
        return res;
    }
    
};

2nd submit [runtime error]:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        cache.resize(mat.size());
        
        long long l = 0, r = 0;
        for (const auto& m : mat) {
            l += m.front();
            r += m.back();
        }
        
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long n = count(mat, 0, mid);
            // cout << mid << ": " << n << endl;
            if (n >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    long long count(vector<vector<int>>& mat, int pos, int val) {
        if (pos >= mat.size()) {
            return 1;
        }
        if (cache[pos].find(val) != cache[pos].end()) {
            return cache[pos][val];
        }
        
        long long res = 0;
        for (int i = 0; i < mat[pos].size(); ++i) {
            if (mat[pos][i] <= val) {
                res += count(mat, pos + 1, val - mat[pos][i]);
            } else {
                break;
            }
        }
        
        return cache[pos][val] = res;
    }
    
    vector<unordered_map<int, long long>> cache;
};

3rd submit [timeout]:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        cache.resize(mat.size());
        
        long long l = 0, r = 0;
        for (const auto& m : mat) {
            l += m.front();
            r += m.back();
        }
        
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long n = count(mat, 0, mid);
            // cout << mid << ": " << n << endl;
            if (n >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    long long count(vector<vector<int>>& mat, int pos, int val) {
        if (pos >= mat.size()) {
            return 1;
        }
        if (cache[pos].find(val) != cache[pos].end()) {
            return cache[pos][val];
        }
        
        long long res = 0;
        for (int i = 0; i < mat[pos].size(); ++i) {
            if (res >= LLONG_MAX / 2) {
                break;
            }
            if (mat[pos][i] <= val) {
                res += count(mat, pos + 1, val - mat[pos][i]);
            } else {
                break;
            }
        }
        
        return cache[pos][val] = res;
    }
    
    vector<unordered_map<int, long long>> cache;
};

4th submit [timeout]:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        cache.resize(mat.size());
        limit = k;
        
        long long l = 0, r = 0;
        for (const auto& m : mat) {
            l += m.front();
            r += m.back();
        }
        
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long n = count(mat, 0, mid);
            // cout << mid << ": " << n << endl;
            if (n >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    long long count(vector<vector<int>>& mat, int pos, int val) {
        if (pos >= mat.size()) {
            return 1;
        }
        if (cache[pos].find(val) != cache[pos].end()) {
            return cache[pos][val];
        }
        
        long long res = 0;
        for (int i = 0; i < mat[pos].size(); ++i) {
            if (res > limit) {
                break;
            }
            if (mat[pos][i] <= val) {
                res += count(mat, pos + 1, val - mat[pos][i]);
            } else {
                break;
            }
        }
        
        return cache[pos][val] = res;
    }
    
    vector<unordered_map<int, long long>> cache;
    int limit = 0;
};

5th submit [passed]:

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        cache.resize(mat.size());
        acc.resize(mat.size() + 1);
        limit = k;
        
        long long l = 0, r = 0;
        for (const auto& m : mat) {
            l += m.front();
            r += m.back();
        }
        
        for (int i = mat.size() - 1; i >= 0; --i) {
            acc[i] += mat[i].front();
            if (i + 1 < mat.size()) {
                acc[i] += acc[i+1];
            }
        }
        
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long n = count(mat, 0, mid);
            // cout << mid << ": " << n << endl;
            if (n >= k) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return l;
    }
    
    long long count(vector<vector<int>>& mat, int pos, int val) {
        if (pos >= mat.size()) {
            return 1;
        }
        if (cache[pos].find(val) != cache[pos].end()) {
            return cache[pos][val];
        }
        
        if (val < acc[pos]) {
            return 0;
        }
        
        long long res = 0;
        for (int i = 0; i < mat[pos].size(); ++i) {
            if (res > limit) {
                break;
            }
            if (mat[pos][i] <= val) {
                res += count(mat, pos + 1, val - mat[pos][i]);
            } else {
                break;
            }
        }
        
        return cache[pos][val] = res;
    }
    
    vector<unordered_map<int, long long>> cache;
    int limit = 0;
    vector<int> acc;
};
Comments (1)