// 演算法 / Algorithm:
//   nums: vector<int> 存實際值 / vector storing the actual values
//   pos : unordered_map<int,int> val -> nums 的 index / map from value to its index
//   刪除採用 swap-with-last + pop_back / removal swaps target with last then pop_back

#include <vector>          // std::vector / 動態陣列容器
#include <unordered_map>   // std::unordered_map / 雜湊表容器
#include <cstdlib>         // std::rand / C 風格隨機數

class RandomizedSet {
private:
    std::vector<int> nums;                          // 動態陣列存元素 / array of current elements
    std::unordered_map<int, int> pos;               // val -> nums 的 index / map: value to its index in nums

public:
    RandomizedSet() {}                              // 預設建構即可（容器自帶初始化） / default ctor; containers self-initialize

    bool insert(int val) {
        if (pos.count(val)) return false;           // 已存在就拒絕 / reject if already present
        pos[val] = nums.size();                     // 新元素的 index 是目前 size / its index will be the current size
        nums.push_back(val);                        // 追加到陣列尾端 / append at the end
        return true;                                // 成功插入 / inserted
    }

    bool remove(int val) {
        auto it = pos.find(val);                    // 用 find 拿到 iterator 避免兩次查找 / single lookup via find
        if (it == pos.end()) return false;          // 找不到就不能刪 / not present, nothing to do

        int idx = it->second;                       // 取得要刪位置 / index of the slot to vacate
        int lastVal = nums.back();                  // 取得最後一個值 / grab last value of nums

        nums[idx] = lastVal;                        // 把最後一個值搬到要刪位置 / move last value into the hole
        pos[lastVal] = idx;                         // 更新被搬動值的新 index / update map for the moved value
        nums.pop_back();                            // 陣列尾端去掉一個 / shrink the array by one
        pos.erase(it);                              // 從雜湊表抹掉 val / erase val from the map
        return true;                                // 成功刪除 / removed
    }

    int getRandom() {
        return nums[std::rand() % nums.size()];     // 隨機 index 後直接取值 / O(1) random index then index lookup
    }
};