#line 5388 "smat.w"

#line 5507 "smat.w"
#include "smat.h"
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <sstream>
#include <utility>
#include <vector>
#ifdef linux
#include <getopt.h>
#endif
#line 5388 "smat.w"

using namespace std;


#line 755 "smat.w"
template <typename T>
pair<T, T> minmax_twopass(const T& first, const T& last)
{
  return pair<T, T>(min_element(first, last), max_element(first, last));
}
#line 5391 "smat.w"


#line 766 "smat.w"
template <typename T>
pair<T, T> minmax_onepass(T first, const T& last)
{
  T min = first, max = first;
  while (++first != last)
    {
      if (*first < *min)
        min = first;
      else if (*max < *first)
        max = first;
    }
  return pair<T, T>(min, max);
}
#line 5392 "smat.w"


#line 787 "smat.w"

template <typename T>
inline void minmax_helper(const T& small, const T& large, T& min, T& max)
{
  if (*small < *min)
    min = small;
  if (*max < *large)
    max = large;
}

template <typename T>
pair<T, T> minmax_fewercmp(T first, const T& last)
{
  T min = first, max = first;
  for (; first + 2 <= last; first += 2)
    {
      if (*first < *(first + 1))
        minmax_helper(first, first + 1, min, max);
      else
        minmax_helper(first + 1, first, min, max);
    }

  if (first + 1 == last)
    minmax_helper(first, first, min, max);

  return pair<T, T>(min, max);
}
#line 5393 "smat.w"


#line 3409 "smat.w"
template <typename T>
pair<T, T> minmax_fewercmp_cse(T first, T last)
{
  T min = first, max = first;
  T first_plus_one = first + 1;
  last -= 2;
  for (; first <= last; first += 2, first_plus_one += 2)
    {
      if (*first < *first_plus_one)
        minmax_helper(first, first_plus_one, min, max);
      else
        minmax_helper(first_plus_one, first, min, max);
    }

  if (first_plus_one == last + 2)
    minmax_helper(first, first, min, max);

  return pair<T, T>(min, max);
}
#line 5394 "smat.w"


#line 9187 "smat.w"
template <typename T>
static bool lazy_atoi(T* dst, const char *s)
{
  std::istringstream ist(s);
  return (!(ist >> *dst).fail() && (ist >> std::ws).eof()) ? true : false;
}
#line 5395 "smat.w"


#line 9204 "smat.w"
#include <boost/random.hpp>

template <typename Elem>
class genrand_limit {
  
#line 9226 "smat.w"
  class mt19937_new_initializer {
    unsigned x, c;
  public:
    explicit mt19937_new_initializer(unsigned i = 1) : x(i), c(0) { }
    unsigned operator()()
    { return ++c == 1 ? x : x = (1812433253U * (x ^ (x >> 30)) + c - 1); }
  };
#line 9208 "smat.w"

  mt19937_new_initializer inimt;
  boost::mt19937 genmt;
  double divisor;
public:
  genrand_limit(unsigned seed = 7U,
                Elem u = std::numeric_limits<Elem>::max())
    : inimt(seed), genmt(inimt),
      divisor((std::numeric_limits<unsigned>::max() + 1.0) / (u + 1.0)) {}
  Elem operator()() { return static_cast<Elem>(genmt() / divisor); }
};
#line 5396 "smat.w"


#line 5408 "smat.w"
static void usage(char *progname, int status)
{
  if (status != 0)
    cerr << "Try `" << progname << " -h' for more information.\n";
  else
    {
      cout << "Usage: " << progname << " [OPTION]... ALGO NELEM\n\
Generate NELEM random numbers and print the minimux and maximum elements.\n\
ALGO must be one of `twopass', `onepass', `fewercmp', and `cse'.\n\
\n\
  -s NUM    random seed\n\
  -h        display this help and exit\n";
    }

  exit(status);
}
#line 5397 "smat.w"


#line 5432 "smat.w"
int main(int argc, char *argv[])
{
  unsigned seed = 3U, nelem;

  ios::sync_with_stdio(false);
  cin.tie(0);

  
#line 5464 "smat.w"
  {
    int optc;
    while ((optc = getopt(argc, argv, "hs:")) != -1)
      {
        switch (optc)
          {
          case 'h':
            usage(argv[0], EXIT_SUCCESS);
            break;
  
          case 's':
            if (! lazy_atoi(&seed, optarg))
              {
                cerr << argv[0] << ": invalid seed `" << optarg << "'\n";
                return EXIT_FAILURE;
              }
            break;
  
          default:
            usage(argv[0], EXIT_FAILURE);
            break;
          }
      }
  }
  
  if (optind != argc - 2)
    usage(argv[0], EXIT_FAILURE);
  
  if (argv[optind][0] != 't' && argv[optind][0] != 'o'
      && argv[optind][0] != 'f' && argv[optind][0] != 'c')
    {
      cerr << argv[0] << ": invalid algorithm `" << argv[optind] << "'\n";
      return EXIT_FAILURE;
    }
  
  if (! lazy_atoi(&nelem, argv[optind + 1]) || nelem == 0)
    {
      cerr << argv[0] << ": invalid number of elements `"
           << argv[optind + 1] << "'\n";
      return EXIT_FAILURE;
    }
#line 5439 "smat.w"


  vector<unsigned> v(nelem);
  generate(v.begin(), v.end(), genrand_limit<unsigned>(seed));

  typedef vector<unsigned>::iterator iter;
  pair<iter, iter> p;

  if (argv[optind][0] == 't')
    p = minmax_twopass(smat<iter>(v.begin()), smat<iter>(v.end()));
  else if (argv[optind][0] == 'o')
    p = minmax_onepass(smat<iter>(v.begin()), smat<iter>(v.end()));
  else if (argv[optind][0] == 'f')
    p = minmax_fewercmp(smat<iter>(v.begin()), smat<iter>(v.end()));
  else
    p = minmax_fewercmp_cse(smat<iter>(v.begin()), smat<iter>(v.end()));

  cerr << *p.first << ", " << *p.second << '\n';
  return EXIT_SUCCESS;
}
#line 5398 "smat.w"