fork(2) download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_map>
  4. #include <algorithm>
  5. #include <stdlib.h>
  6.  
  7. typedef struct node{
  8. 	int key;
  9. 	int size;
  10. 	struct node *left;
  11. 	struct node *right;
  12. }tree;
  13.  
  14. tree * insert(tree *root, int value){
  15. 	if(root == NULL){
  16. 		root = (tree *)malloc(sizeof(tree));
  17. 		root->key = value;
  18. 		root->left = root->right = 0;
  19. 		root->size = 1;
  20. 		return root;
  21. 	}
  22. 	root->size++;
  23. 	if(value > root->key)
  24. 		root->right = insert(root->right, value);
  25. 	else
  26. 		root->left = insert(root->left, value);
  27. 	return root;
  28. }
  29.  
  30. tree * os_select(tree *root, int i){
  31. 	int r;
  32. 	if (root->left)
  33. 	    r = root->left->size + 1;
  34. 	else
  35. 		r = 1;
  36. 	if(i == r) return root;
  37. 	else{
  38. 		if(i < r) return os_select(root->left, i);
  39. 		else	  return os_select(root->right, i - r);
  40. 	}
  41. }
  42.  
  43. void init_container(tree *container, const std::size_t n){
  44. 	std::size_t weight;
  45. 	for(std::size_t i = 0; i < n; i++){
  46. 		std::cin >> weight;
  47. 		container = insert(container, weight);
  48. 	}
  49. }
  50.  
  51. void init_warehouse(std::priority_queue<std::size_t> *wh, const std::size_t m){
  52. 	std::size_t weight;
  53. 	for(std::size_t i = 0; i < m; i++){
  54. 		std::cin >> weight;
  55. 		wh->push(weight);
  56. 	}
  57. }
  58.  
  59. void update_container(tree *container, std::priority_queue<std::size_t> warehouse){
  60. 	if(!warehouse.empty()){
  61. 		int piece_weight = warehouse.top();
  62. 		warehouse.pop();
  63.  
  64. 		container = insert(container, piece_weight);
  65. 	}
  66. }
  67.  
  68. int main(){
  69. 	std::size_t n, m, a, b, k;
  70. 	register int x = 0;
  71. 	std::priority_queue<std::size_t> warehouse;
  72. 	tree  *container = NULL;
  73. 	tree *piece = NULL;
  74.  
  75. 	std::cin >> n;	//N кусков в контейнере
  76. 	std::cin >> m;	//M кусков в хранилище
  77. 	std::cin >> a;
  78. 	std::cin >> b;
  79. 	std::cin >> k;	//K кусков, выданных покупателю
  80.  
  81.  
  82. 	//Загружаем куски в соответствующие хранилища
  83. 	init_container(*&container, n);
  84. 	init_warehouse(&warehouse, m);
  85.  
  86. 	while(k--){
  87. 		// Ищем кусок с номером x в порядке возрастания
  88. 		piece = os_select(container, x);
  89. 		std::cout << piece->key << " ";
  90. 		update_container(*&container, warehouse);
  91. 	}
  92. }
Runtime error #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
3 2 1 1 2
5 1 3
4 2
stdout
copy 
Standard output is empty
https://ideone.com/RdV1lR
language:
C++14 (gcc 8.3)
created:
9 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!