#include <cassert>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <chrono>
#include <algorithm>
#include <cmath>
#include <iomanip>

// В данной лабораторной работе можно не писать каждый раз "std::".
using namespace std;

// ---------------------------------------------------------------------------
// Задание 1. Сумма элементов массива.

double MagicSum(double a, double b, double& error) {
  double sum = a + b;
  double error_a = (a - (sum - b));
  double error_b = (b - (sum - a));
  error = error_a + error_b;
  return sum;
}

double GetSum(const vector<double>& values) {
  if (values.size() == 0) {
    return 0;
  }
  double sum = values[0];
  double error = 0;
  for (int32_t i = 1; i < values.size(); i++) {
    sum = MagicSum(sum, values[i] + error, error);
  }
  return sum;
}

// ---------------------------------------------------------------------------
// Задание 2. Магическая сумма матрицы.

bool BitCount(uint32_t number) {
  int bit_count = 0;
  while (number > 0) {
    if (number & 1) {
      bit_count++;
    }
    number >>= 1;
  }
  return bit_count <= 4;
}

uint32_t GetMagicXor(const vector<uint32_t>& values) {
  uint32_t magic_xor_value = 0;
  for (uint32_t value : values) {
    if (BitCount(value)) {
      magic_xor_value ^= value;
    }
  }
  return ~magic_xor_value;
}

vector<uint32_t> GetMagicXor(const vector<vector<uint32_t>>& values) {
  vector<uint32_t> result(values.size());
  for (int32_t i = 0; i < values.size(); i++) {
    result[i] = GetMagicXor(values[i]);
  }
  return result;
}

// ---------------------------------------------------------------------------
// Задание 3. Точка на плоскости

// Функция возвращает номер Вашего варианта.
int GetVariant() {
  return 1;
}

const double eps = 1e-9;

// Функция определяет, лежит ли точнка в указанной области.
int DoubleComparator(double a, double b) {
  if (fabs(a - b) < eps)
    return 0;
  if (a - b > 0)
    return 1;
  return -1;
}

int CompareWithCircle(double x, double y) {
  return DoubleComparator(x * x + y * y, 15);
}

int CompareWithLine(double x, double y) {
  return DoubleComparator(y, -x + 3);
}

int CompareWithParabola(double x, double y) {
  return DoubleComparator(y, x * x + 2 * x - sqrt(15));
}

int CompareWithCos(double x, double y) {
  return DoubleComparator(y, cos(2 * x));
}

bool IsPointInArea(double x, double y) {
  if (CompareWithParabola(x, y) >= 0 && CompareWithCircle(x, y) <= 0
      && CompareWithLine(x, y) <= 0) {
    if (DoubleComparator(x, 0) >= 0 && CompareWithCos(x, y) <= 0) {
      return 1;
    }
    if (DoubleComparator(y, 0) >= 0 && DoubleComparator(x, 0) <= 0) {
      if (CompareWithCos(x, y) >= 0) {
        return 1;
      }
      if (CompareWithCos(x, y) <= 0
          && DoubleComparator(x, -3.0 * acos(-1) / 4.0) <= 0)
        return 1;
    }
  }
  return 0;
}


// ---------------------------------------------------------------------------
// Задание 4. Сортировки

void BubbleSort(vector<string>& values) {
  for (int32_t i = 0; i < values.size(); i++) {
    for (int32_t j = 0;
         j < static_cast<int32_t>(values.size()) - i - 1; j++) {
      if (values[j] > values[j + 1]) {
        swap(values[j], values[j + 1]);
      }
    }
  }
}

void SelectionSort(vector<string>& values) {
  for (int i = 0; i < static_cast<int32_t>(values.size()) - 1; i++) {
    int k = i;
    for (int j = i + 1; j < values.size(); j++) {
      if (values[j] < values[k]) {
        k = j;
      }
    }
    swap(values[i], values[k]);
  }
}

void ShakerSort(vector<string>& values) {
  int left_index = 0;
  int right_index = static_cast<int32_t>(values.size()) - 1;
  while (left_index < right_index) {
    for (int i = left_index; i < right_index; i++) {
      if (values[i + 1] < values[i]) {
        swap(values[i + 1], values[i]);
      }
    }
    right_index--;

    for (int i = right_index; i > left_index; i--) {
      if (values[i] < values[i - 1]) {
        swap(values[i - 1], values[i]);
      }
    }
    left_index++;
  }
}

void ExcahngeSort(vector<string>& values) {
  for (int i = 0; i < values.size(); i++) {
    for (int j = i + 1; j < values.size(); j++) {
      if (values[i] > values[j]) {
        swap(values[j], values[i]);
      }
    }
  }
}

void WriteAlgoStat(string algo_name, double working_time) {
  cout << algo_name << " working time is " << working_time << "s\n";
}

string GenerateString(int) {
//    if (size == -1) {
//        size = rand_r() % 20000;
//    }
  string result = "";
//    for (int i = 0; i < size; i++) {
//        result.push_back((char) (rand() % 256 - 128));
//    }
  return result;
}

void GenerateArray(vector<string>& array, int size_of_strings) {
  for (int i = 0; i < array.size(); i++) {
    array[i] = GenerateString(size_of_strings);
  }
}

void GenerateStatistics(int size, int size_of_strings = -1) {
  cout << "Size of array:" << size << " Size of strings:";
  if (size_of_strings == -1) {
    cout << "RANDOM\n";
  } else {
    cout << size_of_strings << '\n';
  }

  vector<string> line(size);
  GenerateArray(line, size_of_strings);
  vector<string> example = line;

  auto start = chrono::high_resolution_clock::now();
  BubbleSort(line);
  auto finish = chrono::high_resolution_clock::now();
  WriteAlgoStat("BubbleSort",
                static_cast<double>(std::chrono::duration<double>
                    (finish - start).count()));
  line = example;

  start = chrono::high_resolution_clock::now();
  SelectionSort(line);
  finish = chrono::high_resolution_clock::now();
  WriteAlgoStat("SelectionSort",
                static_cast<double>(std::chrono::duration<double>
                    (finish - start).count()));
  line = example;

  start = chrono::high_resolution_clock::now();
  ExcahngeSort(line);
  finish = chrono::high_resolution_clock::now();
  WriteAlgoStat("ExcahngeSort",
                static_cast<double>(std::chrono::duration<double>
                    (finish - start).count()));
  line = example;

  start = chrono::high_resolution_clock::now();
  ShakerSort(line);
  finish = chrono::high_resolution_clock::now();
  WriteAlgoStat("ShakerSort",
                static_cast<double>(std::chrono::duration<double>
                    (finish - start).count()));
  line = example;
}

// ---------------------------------------------------------------------------
// Задание 5. Бинарный поиск

int FindRecursively(const vector<int>& values, int search_var,
                    int l, int r) {
  if (values.size() == 0)
    return -1;
  int m = (r + l + 1) / 2;
  if (l == r) {
    if (values[l] == search_var)
      return l;
    return -1;
  }
  if (values[m] > search_var)
    return FindRecursively(values, search_var, l, m - 1);
  return FindRecursively(values, search_var, m, r);
}

int FindRecursively(const vector<int>& values, int search_var) {
  return FindRecursively(values, search_var, 0, values.size() - 1);
}

int FindIteratively(const vector<int>& values, int search_var) {
  if (values.size() == 0)
    return -1;
  int l = 0;
  int r = static_cast<int32_t>(values.size()) - 1;
  int m = 0;
  while (l != r) {
    m = (l + r + 1) / 2;
    if (values[m] > search_var) {
      r = m - 1;
    } else {
      l = m;
    }
  }
  if (values[l] == search_var)
    return l;
  return -1;
}

#ifndef IGNORE_SOLUTION_MAIN

int main() {
  // ---------------------------------------------------------------------
  // Тут Вы можете написать код для тестирования Вашего решения.
  // При проверке в системе всё содержимое
  // в данном блоке будет игнорироваться.

  // Ниже даны некоторые очевидные тесты для демонстрации принципа работы.
  // Разумеется, они не покрывают все случаи, но позволяют понять формат,
  // в котором будут использоваться написанные Вами функции.

  {
    // Задание 1.
    // std::vector<double> values = {1, 1.5 - 42.42};
    // double values_sum = GetSum(values);
    // assert(values_sum == -39.92);
  }
  {
    // Задание 2.
    // std::vector<uint32_t> input_1d = {0x1111, 0x0111, 0x0011, 0x0001};
    // uint32_t output_1d = GetMagicXor(input_1d);
    // assert(output_1d == 0xFFFFEFEF);
    //
    // auto result = GetMagicXor(
    //     {
    //         {0x1111, 0x0111, 0x0011, 0x0001,},
    //         {0x0000FFFF, 0x11111111, 0x01010101, 0x0F000F00,},
    //     });
    // assert(result.size() == 2);
    // assert(result[0] == 0xFFFFEFEF);
    // assert(result[1] == 0xFEFEFEFE);
  }
  {
    // Задание 3.
    // assert(GetVariant() == -1);
    ofstream fout("output.txt");
    for (double y = 5; y >= -5; y -= 0.02) {
      for (double x = -5; x <= 5; x += 0.02) {
        fout << IsPointInArea(x, y) << " ";
      }
      fout << '\n';
    }
    IsPointInArea(-3.0, 0.5);
  }
  GenerateStatistics(10000, 1);
  GenerateStatistics(10000);
  {
    // Задание 4.
    // vector<string> values = {
    //     "abacabadabacaba",
    //     "abacaba",
    //     "aaaaaaa",
    // };
    // SelectionSort(values);
    // ExcahngeSort(values);
    // BubbleSort(values);
    // ShakerSort(values);
    // assert(values == vector<string>(
    //     {"aaaaaaa", "abacaba", "abacabadabacaba"}));
  }
  {
    // Задание 5.
    // vector<int> values = {1, 2, 3, 4, 5};
    //
    // auto start = std::chrono::high_resolution_clock::now();
    // assert(FindRecursively(values, 3) == 2);
    // assert(FindRecursively(values, 42) == -1);
    // auto finish = std::chrono::high_resolution_clock::now();
    // cout << "Recursive search test finished in "
    //      << std::chrono::duration<double>(finish - start).count()
    //      << " seconds.\n";
    //
    // start = std::chrono::high_resolution_clock::now();
    // assert(FindIteratively(values, 3) == 2);
    // assert(FindIteratively(values, 42) == -1);
    // finish = std::chrono::high_resolution_clock::now();
    // cout << "Iterative search test finished in "
    //      << std::chrono::duration<double>(finish - start).count()
    //      << " seconds.\n";
  }

  // ---------------------------------------------------------------------
}

#endif