Garavitey's blog

By Garavitey, history, 12 months ago, In English

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?

code of unordered_map

code for map

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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