This is a very simple question, I tried this because I thought searching in the set takes logarithmic time, thinking it’ll pass easily. Why it is giving TLE?
std::set has a huge constant factor because it implements a binary search tree. The constant factor is not to be underestimated. Never use set when it is not strictly necessary. Consider reading this article: http://lafstern.org/matt/col1.pdf
Edit: same applies to map.
You didn’t need an ordered set as the input is already lexicographically sorted. Each insertion in set takes O(logn) time, making it O(nlogn*|s|), which is quite big!
Also, every insertion in set takes logn time, thus n*logn- complexity f insertion which can maximum be 1000log(100) which is 2000, now searching takes logn, which can maximum be log(100)=2. These much operations can be executed in 1 sec easily I suppose.
^^ also tles as expected, insertion in map is O(logn) aswell!
As I can see in your code, you are nowhere calling binarysearch function or m i missing something?
this guy’s solution got accepted using a map. He has used scanf instead of cin
http://www.codechef.com/viewsolution/6004729
It’s also the case in one of my solution, but the only difference I see in ACed ones, is the use of scanf() etc and strcmp(). Nothing else… Try changing to that once…
just the difference of scanf and cin
In this case the problem seems to be slow IO.
But everything I said still applies and I wouldn’t recommend using a set when sorting an array and doing binary search works.
In your code also I suppose? 
This is just kind of damn thing, oh damn_me, we spend so much of time thinking where we went wrong and then the mistake which comes out to be is this “use scanf() and u’ll get AC”!!!
I didn’t participate in this contest.
Just always use scanf and you won’t come across such errors.
Yeah, I know, and i always try my TLE submission replacing it with scanf(), this was just a by chance that I didn’t try it again and that was the only thing I was supposed to do.