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

shitty.Mishka Is it possible to solve this problem without sorting? [7] // Задача 1105. Раскраска наблюдателей 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?

I have answers to all your questions :) Re: Is it possible to solve this problem without sorting? [3] // Задача 1105. Раскраска наблюдателей 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 ) ;)

shitty.Mishka Thank you very much! I used Merge Sort and I've just got and accepted. I appreciate your help a lot :) [1] // Задача 1105. Раскраска наблюдателей 16 ноя 2001 00:31

Huang Yizheng Who said that qsort is an O(n^2) algorithm?I got accepted in 0.06sec using qsort. // Задача 1105. Раскраска наблюдателей 17 янв 2002 05:35

liuchang Re: Is it possible to solve this problem without sorting? // Задача 1105. Раскраска наблюдателей 11 июн 2004 17:58

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

KING_OF_AZE Re: Is it possible to solve this problem without sorting? // Задача 1105. Раскраска наблюдателей 14 фев 2007 19:52

you can use the quick sort in short algorithim

Fly [Yaroslavl_SU] Re: Is it possible to solve this problem without sorting? [1] // Задача 1105. Раскраска наблюдателей 5 апр 2007 00:14

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

Alias (Alexander Prudaev) Re: Is it possible to solve this problem without sorting? // Задача 1105. Раскраска наблюдателей 5 апр 2007 08:52

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

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

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