Hello Codeforces community,

I recently encountered a performance difference while solving a problem using an unordered_set and a vector, and I would like to seek some insights on this matter.

In my solution, I initially implemented the logic using an unordered_set to keep track of element occurrences. However, to my surprise, this implementation resulted in a Time Limit Exceeded (TLE) verdict. Curious about the issue, I refactored the code to use a vector instead, and the TLE issue was resolved.

Solution with Unorder_Set: https://cses.fi/problemset/result/6298544/ Solution with Vector: https://cses.fi/problemset/result/6298541/ Problem: https://cses.fi/problemset/task/1141/

Here are the relevant parts of the two code snippets:

First implementation with Unordered_Set:

while (head + 1 < n && occ.find(id[head + 1]) == occ.end())
{
    ++head;
    occ.insert(id[head]);
    ++count;
}

while (head + 1 < n && occ.find(id[head + 1]) == occ.end()) { ++head; occ.insert(id[head]); ++count; }

Second implementation with Vector:

vector<bool> occ(n, false);

while (head + 1 < n && !occ[id[head + 1]])
{
    ++head;
    occ[id[head]] = true;
    ++count;
}

I expected both implementations to have similar performance, as the time complexity of accessing elements in an unordered_set and a vector is generally O(1). However, it seems that the implementation with unordered_set resulted in a TLE, while the vector implementation passed the tests successfully.

I would greatly appreciate it if someone could shed some light on why this performance difference occurred. Are there any particular reasons or considerations that make unordered_set less performant in this scenario? Any insights or suggestions would be valuable to me.

Thank you for your time and expertise.