UVA – 10810 – Ultra-QuickSort

  • Problem Statement : http://uva.onlinejudge.org/external/108/10810.html
  • Type : Inversion Index Problem / Merge Sort
  • Solution :
    •  this problem can be solved using edited merge sort to count the no of inversions that occurs because the input set is really large.
    • or you can  use a tree structure to simulate the insertion process, keeping track of the no of nodes to the right of the node, and using it during every insertion. to keep track of how many nodes you have been swapped with.
#include <iostream>
#include <stdio.h>
using namespace std;
long int ans = 0;
struct Node {
	int n, right;
	Node * child[2];
	Node(int _n) {
		child[0] = child[1] = 0;
		n = _n, right = 1;
	}
};

void insert(Node *& node, int a) {
	if (node) {
		if (a >= node->n)
			node->right++;
		else
			ans += node->right;
		if (a - node->n)
			insert(node->child[a - node->n > 0], a);
	} else
		node = new Node(a);
}

int main() {
	int N, a;
	Node *r = 0;
	while (scanf("%d", &N) == 1 && N && !(ans = 0) && !(r = NULL)) {
		while (N-- && scanf("%d", &a) == 1)
			insert(r, a);
		printf("%ld\n", ans);
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: