10810 - Ultra-QuickSort

[sazzadcsedu]

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.

[seraph]

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[500001];
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;
}

please help me..

[N@$!M]

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.

[Shafaet_du]

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]

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]

Hello
I've got WA

Why?

Here is my code

Code: Select all

AC

[lighted]

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.

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
about the pivot.

I think that straightforward solution with Quicksort will get TLE.