#include <stdio.h>
#include <omp.h>



int main()
{
	int n=4;
	// 2*n = 2^(m+1)
	int m = 2;
	int i, j, k;
	int A[] = { 2, 6, 3, 8 };
	int *P = (int *)malloc(n * sizeof(int));
	int **R = (int **)malloc((2 * n - 1) * sizeof(int *));
	for (i = 0; i < 2 * n - 1; ++i) {
		R[i] = (int *)malloc(n * sizeof(int));
	}

#pragma omp parralel for private(i,j)
	for (i = 0; i <= n - 1; i++)
	{
		for (j = 0; j <= n - 1; j++)
		{
			if (A[i] < A[j])
			{
				R[i + n - 1][j] = 1;
			}
			else
			{
				R[i + n - 1][j] = 0;
			}
		}
	}

#pragma omp parallel for
	for (j = 0; j <= n - 1; j++) {
		for (k = m; k > 0; k--) {
			for (i = (1 << k)-1; i < (1 << (k + 1)) - 1; i = i + 2) {
				R[i/2][j] = R[i][j] + R[i + 1][j];
			}
		}
	}

	for (j = 0; j <= n - 1; j++)
	{
		P[j] = R[0][j];
	}
#pragma omp parallel for
	for (j = 0; j <= n - 1; j++)
	{
		if (j < P[j])
		{
			if (A[P[j]] != A[j])
			{
				int x = A[P[j]];
				A[P[j]] = A[j];
				A[j] = x;
			}
		}
	}


	for (i = 0; i < n; i++)
		printf("%d ", A[i]);
	printf("\n");

	for (i = 0; i < 2 * n - 1; i++) {
		for (j = 0; j < n; j++)
		{
			printf("%d ", R[i][j]);
		}
		printf("\n");
	}
	return 0;
}