Seminar7

#include <iostream>
#include <string>
#include <vector>

int W = 100;
std::vector<std::vector<int>> E{{4, 3}, {}};

int main1() {
  const char* s = "UGATU.ПГНИУ.";
  std::cout << strlen(s) << std::endl;
  const char* t = "PSU";
  char* s2 = const_cast<char *>(s);
  //s2[2] = 'U';

  for (int i = 0; i < 50; ++i) {
    std::cout << s[i] << ' ';
  }

  int a;
  int* v = new int[100000000];
  std::cout << s << std::endl;
  return 0;
}

int main2() {
  const char* s = "Hi\r\nHello\nPrivetPrivetPrivetPrivet\rHo\n";
  std::cout << s << "UGATU and PSU\n";
  std::cout << "Tab\tTa\tT\tTab" << std::endl;
  std::cout << "Backspace\bBacksp\bBack\bBa\b\b\b\b" << std::endl;
  std::cout << "Unicode: \u1245 \u2665" << std::endl;
  std::cout << "Кавычки: \"\'" << std::endl;
  std::cout << std::endl;

  const char* source = "Hello, PSU and UGATU!";
  char* s2 = new char[100];
  int i = 0;
  do {
    s2[i] = source[i];
  } while(source[i++]);

  //s2[8] = 0;
  std::cout << s2;

  return 0;
}

// Disk [        [Seminar7.exe код стат.данные WE]   ..

// ВАП [---------[SeMInar7.exe КОд стАт.данные WE]   [Stack----]  [Куча [v100mb]---] [Явное выделение через АПИ ---]

// RAM [[Stack----]] [S-MI----.--- КО- --А-.------ WE]  [v100mb]

int main3() {
  std::string x = "abra";
  const char* s = x.c_str();
  std::cout << s << std::endl;

  // UB, но работает
  std::cout << x[0] << x[1] << x[2] << x[3] << x[4] << std::endl;
  std::cout << sizeof(x) << std::endl;
  return 0;
}

bool comparator(const std::string &a, const std::string &b) {
  auto cur_a = a.begin();
  auto cur_b = b.begin();

  while (cur_a != a.end() && cur_b != b.end())
    if (*(cur_a++) != *(cur_b++))
      return *(--cur_a) < *(--cur_b);

  return cur_b != b.end();
}

// ab\0
// abdfsl

int main4() {
  std::string a, b;
  std::cin >> a >> b;
  std::cout << (comparator(a, b) ? "YES" : "NO") << std::endl;
  return 0;
}

// Возвращает индекс, где разместится опорный элемент. [l, r)
int Partition(std::vector<int>& v, int l, int r) {
  if (r - l <= 1) return 0;
  const int& pivot = v[r - 1];
  int i = l, j = r - 2;
  while (i <= j) {
    // Не проверяем, что i < n - 1, т.к. a[n - 1] == pivot.
    for (; v[i] < pivot; ++i ) {}
    for (; j >= l && !(v[j] < pivot); --j) {}
    if (i < j) std::swap(v[i++], v[j--]);
  }
  std::swap(v[i], v[r - 1]);
  return i;
}

// xxxxxPxxxxKxPxx
int KStat(std::vector<int>& v, int k) {
  int left = 0, right = v.size();
  while (true) {
    int pivot = Partition(v, left, right);
    if (pivot == k) return v[pivot];
    if (pivot < k) {
      left = pivot + 1;
    } else {
      right = pivot;
    }
  }
}

int main() {
  std::vector<int> v{4, 6, 12, 5, 33, 4, 7, 15, 3};
  std::cout << KStat(v, v.size() / 2) << std::endl;
  return 0;
}