Обсуждение @ 1105. Раскраска наблюдателей @ Timus Online Judge

Is it possible to solve this problem without sorting?

Послано shitty.Mishka 15 ноя 2001 02:10

I'm sure that my algorythm is correct. It's complexity is O
(n log n), because I use quicksort, and then 2 linear
procedures. Why do I get TimeLimitExceed? Is it possible
not to use sorting?

Re: Is it possible to solve this problem without sorting?

Послано I have answers to all your questions :) 15 ноя 2001 12:27

> I'm sure that my algorythm is correct. It's complexity is
O
> (n log n), because I use quicksort, and then 2 linear
> procedures. Why do I get TimeLimitExceed? Is it possible
> not to use sorting?

because complexity of quicksort in worst case is O(n^2)
use heapsort or mergesort and ur program 'll get accepted (
or at least not TimeLimitExceeded ) ;)

Thank you very much! I used Merge Sort and I've just got and accepted. I appreciate your help a lot :)

Послано shitty.Mishka 16 ноя 2001 00:31

Who said that qsort is an O(n^2) algorithm?I got accepted in 0.06sec using qsort.

Послано Huang Yizheng 17 янв 2002 05:35

Re: Is it possible to solve this problem without sorting?

Послано liuchang 11 июн 2004 17:58

Just use Random-Quick-Sort it'll take a little time to run it.

Re: Is it possible to solve this problem without sorting?

Послано KING_OF_AZE 14 фев 2007 19:52

you can use the quick sort in short algorithim

Re: Is it possible to solve this problem without sorting?

Послано Fly [Yaroslavl_SU] 5 апр 2007 00:14

Still AC with O(N^2). ::)
But sorting i use.

Re: Is it possible to solve this problem without sorting?

Послано Alias (Alexander Prudaev) 5 апр 2007 08:52

do as this
#include <algorithm>
using namespace std;

int a[n];
sort(a,a+n);

Обсуждение задачи 1105. Раскраска наблюдателей