class RandomizedCollection {
unordered_map<int,unordered_set<int>> m;
vector<int> vals;
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
bool flag=true;
if(!m[val].empty()) flag=false;
m[val].insert(vals.size());
vals.push_back(val);
return flag;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
auto& vpos=m[val];
if(vpos.empty()) return false;
int pos=*vpos.begin();
vpos.erase(vpos.begin());
if(pos==vals.size()-1) {vals.pop_back();return true;}
swap(vals[pos],vals[vals.size()-1]);
m[vals[pos]].erase(vals.size()-1);
m[vals[pos]].insert(pos);
vals.pop_back();
return true;
}
/** Get a random element from the collection. */
int getRandom() {
if(vals.empty()) return 0;
int pos=random()%vals.size();
return vals[pos];
}
};
/**
* 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();
*/