How to solve it?)

Quick sort with binary search gets TLE on the 10'th test, and binary search tree - on the 9'th one!

I did it!
Hint for all: quicksort + binary search works.

Can you show your code?)
Or send it to my e-mail: 0x6fwhite@gmail.com

I can tell my idea.
a[i] - numbers of people, b[i] - numbers of towns.
I sort it. First sorting - array a, second sorting - if a[i]=a[j] then you must sort b[i] and b[j].
And finally use binary search.
That's all)

Hmm. I do the same) But, I think, I do it some more simple. I use structure <people, year>. I sort the array of this type by people... And then I use binary search. Shit! But it gets TLE! I write my programs in PASCAL. Where do you do it? In C++ ? Maybe it works faster...

Pavel, it doesnt matter, pascal or C++, its depends on only your brains, how your program works..
Your algo seems to be right, but think about your bin.search realization. Try to find endless cycle, for example. Good luck ;)

thanks... I got AC...

Edited by author 08.05.2008 01:10

I just sort the array and use lower bound