## 10810 - Ultra-QuickSort

Moderator: Board moderators

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10810 - Ultra-QuickSort

I did not check your code.But one thing i can say even if ur code avoid run time error, it can't avoid time limit exceed .Input size is 50000.So (n^2) bubble sort cant pass time limit, u have to use (nlogn) sorting algorithm like merge sort.
Best of luck with merge sort.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

seraph
New poster
Posts: 9
Joined: Tue Dec 15, 2009 4:18 pm

### Re: 10810 - Ultra-QuickSort

why i got WA in my code ?

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static long long sw,n;
static long long v;
void gabung(int p,int q,int r)
{
long long n1 = q-p+1;
long long n2 = r-q;
long long i,j;
long long L[n1+1], R[n2+1];
for (i=0;i<n1;i++)
L[i]=v[p+i];
for (j=0;j<n2;j++)
R[j]=v[q+j+1];
i=0;j=0;
L[n1]=1000000000;
R[n2]=1000000000;
for (int k=p;k<=r;k++)
{
if (L[i]<=R[j])
{
v[k]=L[i];
i++;
}
else
{
v[k]=R[j];
j++;
if (L[i]!=1000000000)
sw+=j;
}
}
}
void divide(int awal, int akhir)
{
if (awal < akhir)
{
long long q=(awal+akhir)/2;
divide(awal,q);
divide(q+1,akhir);
gabung(awal,q,akhir);
}
}
int main()
{
int temp;

while (cin>>n)
{
if (n==0)
break;
sw=0;
memset(v,0,sizeof(v));
for (int i=0;i<n;i++)
{
scanf("%lld",&v[i]);
}
divide(0,n-1);
cout<<sw<<endl;
//for (int i=0;i<n;i++)
//    cout<<v[i]<<" ";
//cout<<endl;
}
return 0;
}
``````

N@\$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

### 10810 - Ultra-QuickSort (Data type 'long' is enough)

I've used the Merge Sort approach and got Accepted with the long datatype. So, now a days I think long long is not necessary for this problem.
( <---- 24 November, 2010)

Also got Accepted in the BST approach... but it took greater runtime.
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.

tariqmnasim@gmail.com

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 10810 - Ultra-QuickSort

I got WA until i used LONG LONG.
Try this case:

Code: Select all

``````10
324 123 123 123 213 435 678 234 879 234
0``````
ans 11

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

### Re: 10810 - Ultra-QuickSort

I tried using long too and accepted it mean the judge computer using 64bit now ?
i tried in the 64bit computer and print sizeof(long) and it return 8 which is sizeof(long long) in 32bit computer

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### Re: 10810 - Ultra-QuickSort

Hello
I've got WA

Why?

Here is my code

Code: Select all

``AC``

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10810 - Ultra-QuickSort

Got accepted with mergesort 10810 (11858, 11495, 10327). This problem was useful to learn the way to find number of inversions in O(N*logN) with Divide and Conquer algorithm. gvcormac wrote:
sohel wrote:I also used D&C and got AC in 2.14 seconds..

.. its funny that to solve a quicksort program, one has to implement merge sort.

- It also seems that some managed to solve it taking < 1sec time.
Is there any other method other then the classical merge sort?
The sort in the problem is "quicksort" in name only.

There's a straightforward solution using quicksort. Just count the
number of inversions you have to do when you arrange the elements