Блог пользователя ErenZ

Автор ErenZ, история, 6 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ErenZ (previous revision, new revision, compare).

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    find fuction causes tle in this case ,instead of (mp.find(a) != mp.end()) use (mp[a]>0) and also change else statement like this mp[x-a]=i+1 , so that after all mp[a] will be 0 if value is not inserted,and it will easily checked in program.

    btw, map uses tree structure to find a element while unordered map search element by visiting every element in it .

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks for replying, Is there some article that explains how this complexity of the unordered_map works? I thought it was always O(1).

»
6 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

me (!)