#include<stdio.h>
#include<stdlib.h>
#define Max 500000
#define MaxValue 999999999
long long int A[Max+2],temp[Max+2],R[Max+2],swap,s,n,inf = MaxValue+1;
void merge(long long int numbers[],long long int temp[],long long int left,long long int mid,long long int right)
{
long long int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
swap++;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
void m_sort(long long int numbers[], long long int temp[], long long int left, int right)
{
long long int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void mergeSort(long long numbers[], long long int temp[], long long int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}
int main()
{
long long int i;
while(1)
{
scanf("%lld",&n);
if(!n)break;
i=0;
while(i<n)
{
scanf("%lld",&A);
i++;
}
s=swap=0;
mergeSort(A,temp,n);
//qsort(&a[0],n,sizeof(a[0]),sort);
printf("%lld\n",swap);
//printf("%d\n",s);
}
return 0;
}
is not enough. Imagine, for example, an extreme (non-balanced) case of say:swap++;
Output5
5
2
3
4
1
7
um...scanf is slow? so any replacements?filigabriel wrote:My original program runstechnobug wrote:How fast is your D+C algorithm? What is its idea?in 1.150 seconds
Main idea was already posted by Eduard
I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.
That's me.dpitts wrote:I have a working solution in ~1.3 seconds, but someone has it in .174?
I has already gotten AC with merge sort but now i'm trying to solve this problem using quicksort. However, i'm a little bit confused with cormack's hint . How can I count the number of inversions? I tried it with this idea but I get incorrect answers when the numbers are already sorted.gvcormac wrote: 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.
Code: Select all
#include <stdio.h>
int a[500001];
long long cont;
int particion(int a[],int p, int r)
{
int j,t,i=p-1,x=a[r];
for(j=p; j<=r-1;++j)
{
if( a[j]<=x )
{
++i;
t=a[i];
a[i]=a[j];
a[j]=t;
++cont;
}
}
t=a[i+1];
a[i+1]=a[r];
a[r]=t;
++cont;
return i+1;
}
void quick(int a[],int p, int r)
{
int q;
if(p<r)
{
q=particion(a,p,r);
quick(a,p,q-1);
quick(a,q+1,r);
}
}
int main()
{
int i,n;
while(1)
{
scanf("%i",&n);
if(n==0)
return 0;
for(i=1; i<=n; ++i)
scanf("%i",&a[i]);
cont=0;
quick(a,1,n);
printf("%lli\n",cont);
}
}
When swapping two non-adjacent numbers the number of inversions doesn't have to decrease by 1.Antonio Ocampo wrote:Plz help me!!
Code: Select all
#include <iostream>
using namespace std;
struct node
{
int val;
struct node *left;
struct node *right;
};
long long cnt;
struct node *root;
void right_subtree ( struct node *p )
{
struct node *q;
q = p -> right;
if ( q == NULL ) return;
else
{
cnt ++;
if ( q -> left != NULL )
right_subtree( q -> left );
if ( q -> right != NULL )
right_subtree( q -> right );
}
return;
}
struct node *addtree ( struct node *p , int x )
{
struct node* q;
if ( p == NULL )
{
p = new node();
p -> val = x;
p -> left = p -> right = NULL;
}
else if ( x < p -> val )
{
cnt ++;
right_subtree(p);
p -> left = addtree ( p -> left , x );
}
else
p -> right = addtree ( p -> right , x );
return p;
}
int main ()
{
int n;
while ( scanf ( "%d" , &n ) == 1 && n )
{
root = NULL;
cnt = 0;
for ( int i = 0 ; i < n ; i ++ )
{
int x;
scanf ( "%d" , &x );
root = addtree ( root , x );
}
printf ( "%lld\n" , cnt );
//if ( cnt%2 ) printf ( "Marcelo\n" );
//else printf ( "Carlos\n" );
}
return 0;
}
Code: Select all
int main()
{
int i, n, f = 1;
//freopen("fread.in","r",stdin);
fread(buffer,29999999,1,stdin); // char buffer[30000000];
p = strtok(buffer," \n");
while(p)
{
if(f)
{
n = atoi(p);
i = f = res = 0;
}
else if(i<n)
{
a[i++] = atoi(p);
}
if(i==n)
{
solve(0,n-1);
printf("%lld\n",res);
f = 1;
}
p = strtok(0," \n");
}
return 0;
}
Code: Select all
#include <stdio.h>
long long int number[50000];
long long int bubble_sort(long long int *a,long long int cas)
{
long long int i,j,temp;
int flag=1;
long long int count=0;
for(i=0;( (i<cas-1) && flag) ;i++)
{
flag=0;
for(j=0;j<cas-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=1;
count++;
}
}
}
return (count);
}
int main()
{
long long int count1,cas,i;
while(scanf("%lld",&cas)==1)
{
if(cas==0)
break;
for(i=0;i<cas;i++)
{
scanf("%lld",&number[i]);
}
count1=bubble_sort(&number[0],cas);
printf("%lld\n",count1);
}
return 0;
}