lc381

struct Node {
    int pos;
    int val;
};
class RandomizedCollection {
    using NP=Node*;
    unordered_map<int, vector<Node*>> pos;
    vector<Node*> elements;
    int avail = 0;
public:
    RandomizedCollection() {
    }

    bool insert(int val) {
        bool ret = (pos.count(val) ? pos[val].size() == 0 : true);
        int id = pos[val].size();
        Node* n = new Node{id, val};
        elements.push_back(n);
        pos[val].push_back(n);
        return ret;
    }

    bool remove(int val) {
        bool ret = (pos.count(val) ? pos[val].size() != 0 : false);
        if (ret) {
            auto e_last = elements.back();
            auto tobedelete = pos[val].back();
            int v2 = e_last->val, p2 = e_last->pos;

            swap(*e_last, *tobedelete);
            pos[v2][p2] = tobedelete;

            elements.pop_back();
            pos[val].pop_back();
        }
        return ret;
    }

    int getRandom() {
        int n = elements.size();
        return elements[rand() % n]->val;
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */