fork(11) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void prepare_killer(int* a, int length)
  5. {
  6.     int origidx[length];
  7.     for (int i = 0; i < length; i++)
  8.         origidx[i] = i;
  9.  
  10.     // эмулируем прохождение qsort по плохому пути
  11.     // r будет всё время константой
  12.     int r = length - 1;
  13.  
  14.     // а l будет каждый раз увеличиваться на 1
  15.     for (int l = 0; l < r; l++)
  16.     {
  17.         // так будет выбран pivot:
  18.         int p = (l + r) / 2;
  19.  
  20.         // элементы с индексами l и p поменяются местами
  21.         swap(origidx[l], origidx[p]);
  22.     }
  23.  
  24.     // имея позиции, куда придут данные, можно теперь их расставить:
  25.     for (int i = 0; i < length; i++)
  26.         a[origidx[i]] = i + 1;
  27. }
  28.  
  29. bool qsort_check_failed = false;
  30.  
  31. void qsort_with_check(int *a, int l, int r)
  32. {
  33.     if (l >= r)
  34.         return;
  35.     int x = a[(l + r) / 2];
  36.     int i = l, j = r;
  37.     while (i <= j)
  38.     {
  39.         while (a[i] < x) ++i;
  40.         while (a[j] > x) --j;
  41.         if (i <= j)
  42.         {
  43.             swap(a[i], a[j]);
  44.             ++i, --j;
  45.         }
  46.     }
  47.  
  48.     if (!(l >= j))
  49.     {
  50.         cout << "Mistake: have non-empty first subtask!" << endl;
  51.         qsort_check_failed = true;
  52.     }
  53.     qsort_with_check(a, l, j);
  54.     qsort_with_check(a, i, r);
  55. }
  56.  
  57. int main()
  58. {
  59. 	const int length = 28;
  60. 	int a[length];
  61. 	prepare_killer(a, length);
  62. 	qsort_with_check(a, 0, length - 1);
  63. 	if (!qsort_check_failed)
  64. 	    cout << "killer sequence succeeded" << endl;
  65.     return 0;
  66. }
Success #stdin #stdout 0s 3412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
killer sequence succeeded
https://ideone.com/a9L22p
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!