I was trying to the this question and during that, I used the following code.
void solve() {
read(n); read(x);
map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
this did not give any tle error but when i used the following code
void solve() {
read(n); read(x);
unordered_map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
it was giving tle in the test cases 23 and 24. now I know that both of them are the same except for the use of data structure, but the map should be slower than unordered_map but the opposite is true, why is this happening can anyone explain?
Complexity for ordered map is always O(log(N)) for accessing values..but in unordered map we cant say anything..at worst case even it can go upto O(N)..so generally i prefer to use ordered map to avoid such TLE's
thanks for replying, Is there some article that explains how this complexity of the unordered_map works? I thought it was always O(1).
Blowing up unordered_map, and how to stop getting hacked on it