// Author : TangHanYi

// E-mail : thydeyx@163.com

// Create Date : 16-11-02 17:22:16

// File Name : Insert_Delete_GetRandom_O1_2.cpp

// Desc :

#include<iostream>

using namespace std;

class RandomizedCollection {

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) {

auto result = m.find(val) == m.end();

m[val].push_back(nums.size());

nums.push_back(pair<int, int>(val, m[val].size() - 1));

return result;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

bool remove(int val) {

auto result = m.find(val) != m.end();

if(result)

{

auto last = nums.back();

m[last.first][last.second] = m[val].back();

nums[m[val].back()] = last;

m[val].pop_back();

if(m[val].empty()) m.erase(val);

nums.pop_back();

}

return result;

}

/** Get a random element from the collection. */

int getRandom() {

return nums[rand() % nums.size()].first;

}

private:

vector<pair<int, int>> nums;

unordered_map<int, vector<int>> m;

};

int main()

{

return 0;

}