#define LENGTH 10
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> ret;
        unordered_map<string, int> dict; 
        if (s.length() <= LENGTH) return ret;  
        for (int i = 0; i + 10 <= s.size(); i++) {
            string target(s.substr(i, LENGTH));
            if (dict[target] == 1) ret.push_back(target);
            dict[target] += 1;
        }
        return ret;
    }
    
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ret;
        int curSum = 0;
        vector<int> curVector;
        check(curSum, sum, ret, root,curVector);
        return ret;
    }
    void check(int curSum, int sum, vector<vector<int>>& ret, TreeNode* root, vector<int>& curVector) {
        if (root == NULL) return;
        curSum += root->val;
        curVector.push_back(root->val);
        if (!root->left && !root->right && sum == curSum) ret.push_back(vector<int>(curVector));

        check(curSum, sum, ret, root->left, curVector);
        check(curSum, sum, ret, root->right, curVector);  
        
        curVector.pop_back();
        return;
    }
};

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger * (1 + maxChoosableInteger) < desiredTotal) return false;
        vector<char> states(1<<maxChoosableInteger, 0);
        helper(desiredTotal, states, 0, 1, maxChoosableInteger);
        return states[0] == 1;
    }
    
    void helper(int target, vector<char>& states, int currentState, int currentUser, int count) {
        if (states[currentState] != 0) return;
        
        for (int i = 0; i < count; ++i) {
            if (currentState & (1<<i)) continue; //Skip it when the number is taken.
            if ((i + 1) >= target) {states[currentState] = currentUser; return;} //Satisfy;
            helper(target - (i + 1), states, currentState | (1<<i), -currentUser, count);
            if (states[currentState | (1<<i)] == currentUser) {
                states[currentState] = currentUser;
                return;
            }
        }
        
        states[currentState] = -currentUser;
        return;
    }
};

class Solution {
private:
    bool static compare(const pair<int, int>& left, const pair<int, int>& right) {
        return left.second < right.second;
    }
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        sort(people.begin(), people.end(), compare);
        list<pair<int, int>> ret;
        for (auto iter = people.begin(); iter != people.end(); ++iter) {
            auto iterRet = ret.begin();
            int bigger = iter->second;
            while (iterRet != ret.end()) {
                if (iter->first <= iterRet->first) --bigger;
                if (bigger < 0){ret.insert(iterRet, *iter); break;}
                ++iterRet;
            }
            if (iterRet == ret.end()) ret.insert(iterRet, *iter);
        }
        return vector<pair<int, int>>(ret.begin(), ret.end());
    }
};

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        if (s.size() > 12 || s.size() < 4) return ret;
        int index = 0;
        vector<char> cur;
        check(ret, s, 0, cur, 0);
        return ret;
    }
    bool valid(string& s, int start, int bias) {
        if (bias > 3) return false;
        if (s[start] == '0' && bias > 1) return false;
        if (bias < 3) return true;
        int target = s[start] - '0';
        target = 10 * target + s[start + 1] - '0';
        target = 10 * target + s[start + 2] - '0';
        return (target <= 255);
    }
    
    void check(vector<string>& ret, string& s, int start, vector<char>& cur, int depth) {
        int size = s.size();
        
        if (start == size) {
            if (depth == 4) {
                string s(cur.begin(), cur.end() - 1); //Skip the last '.'
                ret.push_back(s);
            }else
                return;
        }
        
        int bias = 1;
        while (start + bias <= size && bias <= 3) {
            if ( !valid(s, start, bias) ) break;
            cur.push_back(s[start + bias - 1]);
            cur.push_back('.');
            check(ret, s, start + bias, cur, depth + 1);
            cur.pop_back();
            ++bias;
        }
        while (bias > 1) {cur.pop_back(); --bias; }
        return;
    }
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> degree(numCourses, 0);
        vector<vector<int>> graph(numCourses, vector<int>() );
        vector<int> ret;
        for (auto& pa : prerequisites) {
            degree[pa.first] += 1;
            graph[pa.second].push_back(pa.first);
        }
        queue<int> waitingList;
        for (int i = 0; i < numCourses; ++i) {
            if (degree[i] == 0){
                waitingList.push(i);
                ret.push_back(i);
            }
        }
        while (!waitingList.empty()) {
            int item = waitingList.front();
            waitingList.pop();
            vector<int>& lis = graph[item];
            for (int item : lis) {
                --degree[item];
                if (degree[item] == 0) {
                    waitingList.push(item);
                    ret.push_back(item);
                }
            }
        }
        
        for (int i = 0; i < numCourses; ++i)
            if (degree[i] != 0) return vector<int>();
        
        return ret;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        unordered_map<int, unordered_set<int> > adj;
        for (auto& pa : prerequisites) {
            adj[pa.first].insert(pa.second);
        }
        for (int i = 0; i < numCourses; ++i)
            if (adj.find(i) == adj.end())
                for (auto iter = adj.begin(); iter != adj.end(); ++iter)
                    iter->second.erase(i);
        
        while(!adj.empty()) {
            bool flag = false;
            auto iter = adj.begin();
            while(iter != adj.end()) {
                auto cur = iter;
                ++iter;
                if (cur->second.empty()) {
                    flag = true;
                    int key = cur->first;
                    adj.erase(cur);
                    for (auto it = adj.begin(); it != adj.end(); ++it)
                        it->second.erase(key);
                }
            }
            if (!flag && !adj.empty()) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> degree(numCourses, 0);
        vector<vector<int>> graph(numCourses, vector<int>() );
        for (auto& pa : prerequisites) {
            degree[pa.first] += 1;
            graph[pa.second].push_back(pa.first);
        }
        stack<int> waitingList;
        for (int i = 0; i < numCourses; ++i) {
            if (degree[i] == 0){
                waitingList.push(i);
            }
        }
        while (!waitingList.empty()) {
            int item = waitingList.top();
            waitingList.pop();
            vector<int>& lis = graph[item];
            for (int item : lis) {
                --degree[item];
                if (degree[item] == 0) {
                    waitingList.push(item);
                }
            }
        }
        
        for (int i = 0; i < numCourses; ++i)
            if (degree[i] != 0) return false;
        
        return true;
    }
};

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int size = graph.size();
        if (size == 1) return true;
        vector<int> colors(size, 0);
        
        for (int i = 0; i < size; ++i) {
            if (colors[i] != 0) continue;
            if (dfs(i, colors, graph, 1) == false) return false;     
        }
        return true;
    }
    
    bool dfs(int index, vector<int>& colors, vector<vector<int>>& graph, int color) {
        if (colors[index] != 0) return colors[index] == color;
        colors[index] = color;
        vector<int>& near = graph[index];
        for (int item : near) {
            if (dfs(item, colors, graph, -color) == false) return false;
        }
        return true;
    }
};

class MedianFinder {
private:
    vector<double> maxHeap;
    vector<double> minHeap;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        int size = maxHeap.size() + minHeap.size();
        if (size & 1) {
            //Insert to minHeap;
            double maxItem = maxHeap[0];
            if (num >= maxItem) {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
            }else {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                minHeap.push_back(maxHeap[0]);
                pop_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                maxHeap.pop_back();
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
            }
        }else {
            if (minHeap.empty() || num <= minHeap[0]) {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
            } else {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
                maxHeap.push_back(minHeap[0]);
                pop_heap(minHeap.begin(), minHeap.end(), greater<double>());
                minHeap.pop_back();
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                
            }
        }
    }
    
    double findMedian() {
        int size = maxHeap.size() + minHeap.size();
        return size & 1 ? maxHeap[0] : (minHeap[0] + maxHeap[0]) / 2.0; 
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int size = nums.size();
        if (size == 0 || size == 1) return 0;
        int ret = 0;
        findReversePair(nums, 0, size - 1, ret);
        // for (int i = 0; i < size; i++) cout << nums[i] << endl;
        return ret;
    }
    
    void findReversePair(vector<int>& nums, int left, int right, int& ret) {
        // cout << left << " " << right << endl;
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        findReversePair(nums, left, mid, ret);
        findReversePair(nums, mid + 1, right, ret);
        
        //Check the number and sort the array
        int l = left;
        int r = mid + 1;
        while (l <= mid && r <= right) {
            while(l <= mid && nums[l]/2.0 <= nums[r]) {++l; ret += (r - mid - 1);}
            while(r <= right && nums[l]/2.0 > nums[r]) ++r;
        }
        while (l <= mid) {++l; ret += (r - mid - 1);}
        sort(nums.begin()+left, nums.begin()+right+1);
    }
};