#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;
unsigned _stklen = 1048576 * 64;  /* need an 8MB stack */

void stuff (int [], int);
void swap (int &, int &);
void shuffle (int [], int);
void show (int [], int);
void sort (int [], int, int);
void check (int [], int, int, int, int, int, int, int &, int &);


void stuff ( int NumList[], int Size )
{
  for (int lcv=0; lcv<Size; lcv++)
    NumList[lcv] = lcv;
}

void swap (int &oneNum, int &twoNum)
{
  int tmp;
  tmp = twoNum;
  twoNum = oneNum;
  oneNum = tmp;
}

void shuffle ( int NumList[], int Size )
{
  for (int lcv=0; lcv<Size; lcv++) {
    int newLoc=rand() % Size;
    swap ( NumList[lcv], NumList[newLoc] );
  }
}

void show (int NumList[], int Size)
{
  cout << "List contains: " << endl;
  for (int lcv=0; lcv<Size; lcv++)
    cout << NumList[lcv] << endl;
}

void sort (int NumList[], int Sindex, int Eindex)
{
  for ( int lcv=Sindex; lcv<Eindex; lcv++ )
    for (int lcv1=Sindex; lcv1<lcv; lcv1++)
      if (NumList[lcv] < NumList[lcv1])
	swap (NumList[lcv1], NumList[lcv]);
}

void check (int NumArray[], int Sindex, int Eindex,
            int HighCount, int LowCount, int HighBound, int LowBound,
            int & HighMiss, int & LowMiss)
{
  if ( HighCount == 0 ) HighCount = 1;  // Must rank 1.
  if ( LowCount == 0 ) LowCount = 1;    // Must rank 1.
  for (int lcv=Sindex; lcv<Sindex+HighCount; lcv++)
    if (NumArray[lcv] > HighBound-1)
      HighMiss++;
  for (int lcv=Eindex-LowCount; lcv<Eindex; lcv++)
    if (NumArray[lcv] < LowBound)
      LowMiss++;
}


int main(int argc, char *argv[])
{
  int PopSize, SubSize, NumSub, LastSub, HighPct, LowPct;
  int HighSubCount, LowSubCount, HighBorder, LowBorder;
  int HighMissCount, LowMissCount, LowAsHighCount, HighAsLowCount;

  srand(time(0));
  cout << "Population size?: ";
  cin >> PopSize;
  cout << "Subgroup size?: ";
  cin >> SubSize;
  while ( 0 != PopSize % SubSize ) {
    cerr << PopSize << " is not a multiple of " << SubSize <<
      " try again." << endl;
    cout << "Department size?: ";
    cin >> SubSize;
  }
  NumSub = PopSize / SubSize;
  LastSub = PopSize % SubSize;

  int PopArray[PopSize];
  stuff (PopArray, PopSize);
  shuffle (PopArray, PopSize);

  cout << "What percent in high num group?: ";
  cin >> HighPct;

  cout << "What percent in low num group?: ";
  cin >> LowPct;

  HighSubCount=SubSize * (HighPct / 100.0);
  LowSubCount=SubSize * (LowPct / 100.0);
  HighBorder=PopSize * (HighPct / 100.0);
  LowBorder=PopSize - (PopSize * (LowPct / 100.0));

  HighMissCount=0;
  LowMissCount=0;
  for (int lcv=0; lcv<PopSize; lcv+=SubSize) {
    sort(PopArray,lcv,lcv+SubSize);
    check (PopArray, lcv, lcv+SubSize, HighSubCount, LowSubCount,
           HighBorder, LowBorder, HighMissCount, LowMissCount);    
  }
  if (!strcmp (argv[1], "-s"))
    show (PopArray, PopSize);

  int HighTotal, LowTotal;
  HighTotal = HighBorder;
  LowTotal = PopSize * (LowPct / 100.0);
  cout << "Ranked high but not: " << HighMissCount << "   "
       << 100.0 * (float) HighMissCount / (float) PopSize
       << "\% of population  "
       << 100.0 * (float) HighMissCount / (float) HighTotal
       << "\% of high rankings."
       << endl;
  cout << "Ranked low but not: " << LowMissCount << "   "
       << 100.0 * (float) LowMissCount / (float) PopSize
       << "\% of population  "
       << 100.0 * (float) LowMissCount / (float) LowTotal
       << "\% of low rankings."
       << endl;
}