ivplay's blog

Mapping Integers !
By ivplay, 10 years ago, In English
  • I have some integers 6 , 7 , 9. I want to map them (something like grid compression). Then it should be like :-
  • 6 — > 1
  • 7 — > 2
  • 9 — > 3
  • I tried STL map for(i=1..3) M[arr[i]]=0; then for_each(it,map) (*it).second=++hashValue;
  • Unfortunately I got TLE !
  • Then I used a temporary array (The order of my original array is needed) , sorted it and used a binary search to map them and stored them in another array.
  • But it seems like :-
  • 2 extra array + O(n) to Copy main array into temporary array + O(nlg(n)) to sorting this temporary array + O(nlg(n)) to binary search is faster than simple mapping I mentioned first !!!
  • Is it really true or SPOJ's the great ancient Cluster: Pyramid (Intel Pentium III 733 MHz) machine just fooled me !!! I just can't believe it because my IO method is another great SPOJ template used for IO operation which I believe is faster than scanf/printf.
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i always map/compress integers using sort+bsearch. cz i got a lot of tle just becuse of map<int,int> in different ojs

→ Reply