|
|
back to boardHow it can be solved? Posted by Pavel 4 Apr 2008 03:50 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! * Posted by Брэнд 4 Apr 2008 15:28 I did it!
Hint for all: quicksort + binary search works. Re: * Posted by Pavel 4 Apr 2008 18:05 Can you show your code?)
Or send it to my e-mail: 0x6fwhite@gmail.com * Posted by Брэнд 4 Apr 2008 20:30 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) Re: * Posted by Pavel 5 Apr 2008 02:53 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... Re: * 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 ;) Re: * thanks... I got AC...
Edited by author 08.05.2008 01:10 Re: How it can be solved? I just sort the array and use lower bound |
|
|
