fork(1) download
  1. #include <cstdio>
  2. #include <queue>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8. unsigned n; scanf("%u", &n); //количество команд
  9. int* to_sort = new int[n]; //исходный массив
  10. for(int i = 0; i < n; i++)
  11. scanf("%d", to_sort + i);
  12.  
  13. unsigned k; scanf("%u", &k); //количество очередей
  14. queue<int>* sorting_machine = new queue<int>[k]; //массив очередей
  15.  
  16. int *order = new int[n]; //порядок размещения чисел по очередям
  17. for(int i = 0; i < n; i++){
  18. //подходящая очередь либо пуста, либо имеет последний элемент, меньший данного
  19. //найти её номер в массиве
  20. int available = find_if(sorting_machine, sorting_machine + k,
  21. [&](const queue<int> &q){return q.empty() || q.back() <= to_sort[i];}) - sorting_machine;
  22. //если таких очередей нет, то сортировка невозможна
  23. if(available >= k){
  24. puts("NO");
  25. return 0;
  26. }
  27. //добавить элемент массива в одну из очередей
  28. sorting_machine[available].push(to_sort[i]);
  29. order[i] = available + 1;
  30. }
  31.  
  32. puts("YES");
  33. for(int i = 0; i < n; i++){
  34. //вывод порядка размещения исходного массива чисел по очередям
  35. printf("I(%d)\n", order[i]);
  36. }
  37. for(int i = 0; i < n; i++){
  38. //так как и очередей, и элементов мало, найти минимальный доступный элемент
  39. queue<int>* minimum = min_element(sorting_machine, sorting_machine + k,
  40. [&](const queue<int> x, const queue<int> y){
  41. return !x.empty() && !y.empty() && x.front() < y.front();
  42. });
  43. minimum->pop(); //удалить его
  44. //и вывести номер соответствующей очереди
  45. printf("R(%d)\n", minimum-sorting_machine+1);
  46. }
  47. return 0;
  48. }
  49.  
Success #stdin #stdout 0s 3280KB
stdin
Standard input is empty
stdout
YES