OJ Board

Code: Select all

#include <iostream>

using namespace std;

int a[10000];
int b[10000];
int last = 9999;

int L[10000];
int R[10000];

int infinity = 1000001;

void merge(int p, int q, int r) {

		int n1 = q - p + 1;
		int n2 = r - q;

		for(int i=1; i<=n1; i++)
			L[i] = a[p + i -1];

		for(int j=1; j<=n2; j++)
			R[j] = a[q + j];

		L[n1+1] = infinity;
		R[n2+1] = infinity;

		int l_i = 1;
		int r_j = 1;

		for(int k = p; k<= r; k++) {

			if(L[l_i] <= R[r_j]) {
				a[k] = L[l_i];
				l_i++;
			} else {
				a[k] = R[r_j];
				r_j++;
			}
		}
}

void msort(int p, int r) {
	
	if(p < r) {
		int q = (p+r)/2;

		msort(p, q);
		msort((q+1), r);
		merge(p, q, r);
	}
}

int find_big(int n) {

	int res = -1;

	for(int i=(n-1); i>=0; i--) {
		if(b[i]>0) {
			res = i;
			break;
		}
	}

	return res;
}

void main() {

	int n;

	int no_line = 1;

	while(cin>>n) {
		
		if(n == 0)
			break;

		if(no_line != 1)
			cout<<endl;

		no_line = 2;

		for(int i=0; i<n; i++)
			cin>>a[i];

		msort(0, (n-1));

		for(int i=0; i<n; i++)
			b[i] = a[i];
		
		int stat = find_big(n);
		int pass = 0;
		int max;

		while(stat >= 0) {
			
			max = b[stat];
			b[stat] = -1;
			
			for(int i=(stat-1); i>=0; i--) {

				if((b[i] > 0) && (b[i] < max)) {
					max = b[i];
					b[i] = -1;
				}
			}

			pass++;
			stat = find_big(n);
		}
		
		cout<<pass<<endl;
		
		//this should not be accepted!!!
		for(int i=0; i<n; i++)
			cout<<a[i]<<endl;
	}
}