fork download
copy 
  1. #include <algorithm>
  2. //#include <fstream>
  3. #include <array>
  4. #include <iostream>
  5. #include <memory>
  6.  
  7. struct Level;
  8.  
  9. struct Item
  10. {
  11. 	Item() : id(0) {}
  12.  
  13. 	int id;
  14.  
  15. 	std::shared_ptr<Level> level;
  16.  
  17. 	std::shared_ptr<Item> next;
  18. 	std::shared_ptr<Item> prev;
  19.  
  20. 	std::shared_ptr<Item> left;
  21. 	std::shared_ptr<Item> right;
  22. };
  23.  
  24. struct Level
  25. {
  26. 	Level() : size(0), nConnUp(0), nConnDown(0) {}
  27.  
  28. 	int size;
  29. 	int nConnUp;
  30. 	int nConnDown;
  31.  
  32. 	std::shared_ptr<Item> first;
  33. 	std::shared_ptr<Item> last;
  34. };
  35.  
  36. class Sequence
  37. {
  38. public:
  39. 	Sequence()
  40. 	{
  41. 		for (auto i = 0; i < 100; ++i)
  42. 			mLevels[i] = std::make_shared<Level>();
  43. 	}
  44.  
  45. 	void add(int i)
  46. 	{
  47. 		auto item = std::make_shared<Item>();
  48. 		item->id = i;
  49. 		item->prev = mSeqLast;
  50. 		item->level = mLevels[i];
  51.  
  52. 		if (nullptr == mSeqLast)
  53. 			mSeqFirst = item;
  54. 		else
  55. 			mSeqLast->next = item;
  56.  
  57. 		item->prev = mSeqLast;
  58. 		mSeqLast = item;
  59.  
  60. 		auto level = mLevels[i];
  61.  
  62. 		if (nullptr == level->first)
  63. 			level->first = item;
  64. 		else
  65. 			level->last->right = item;
  66.  
  67. 		if (item->prev)
  68. 		{
  69. 			if (item->prev->id < item->id)
  70. 			{
  71. 				++level->nConnUp;
  72. 				++item->prev->level->nConnDown;
  73. 			}
  74. 			else if (item->prev->id > item->id)
  75. 			{
  76. 				++level->nConnDown;
  77. 				++item->prev->level->nConnUp;
  78. 			}
  79. 		}
  80.  
  81. 		item->left = level->last;
  82. 		level->last = item;
  83.  
  84. 		++level->size;
  85. 	}
  86.  
  87. 	void sort()
  88. 	{
  89. 		std::sort(mLevels.begin(), mLevels.end(), [](std::shared_ptr<Level> a, std::shared_ptr<Level> b) -> bool
  90. 		{
  91. 			return a->size > b->size;
  92. 		});
  93. 	}
  94.  
  95. 	void optimize()
  96. 	{
  97. 		for (auto i = 0; i < 100; ++i)
  98. 		{
  99. 			auto level = mLevels[i];
  100.  
  101. 			if (level->size < level->nConnDown ||
  102. 				level->size < level->nConnUp)
  103. 			{
  104. 				auto item = level->first;
  105. 				while (nullptr != item)
  106. 				{
  107. 					if (item == mSeqFirst)
  108. 					{
  109. 						mSeqFirst = item->next;
  110. 					}
  111.  
  112. 					if (item == mSeqLast)
  113. 					{
  114. 						mSeqLast = item->prev;
  115. 					}
  116.  
  117. 					if (nullptr != item->prev)
  118. 					{
  119. 						if (item->prev->id < item->id)
  120. 							--item->prev->level->nConnDown;
  121. 						else if (item->prev->id > item->id)
  122. 							--item->prev->level->nConnUp;
  123. 						item->prev->next = item->next;
  124. 					}
  125.  
  126. 					if (nullptr != item->next)
  127. 					{
  128. 						if (item->next->id < item->id)
  129. 							--item->next->level->nConnDown;
  130. 						else if (item->next->id > item->id)
  131. 							--item->next->level->nConnUp;
  132. 						item->next->prev = item->prev;
  133. 					}
  134.  
  135. 					if (nullptr != item->left)
  136. 					{
  137. 						item->left->right = item->right;
  138. 					}
  139.  
  140. 					if (nullptr != item->right)
  141. 					{
  142. 						item->right->left = item->left;
  143. 					}
  144.  
  145. 					item = item->right;
  146. 				}
  147.  
  148. 				level->size = 0;
  149. 				level->nConnDown = 0;
  150. 				level->nConnUp = 0;
  151. 				level->first = nullptr;
  152. 				level->last = nullptr;
  153. 			}
  154. 		}
  155. 	}
  156.  
  157. 	void print()
  158. 	{
  159. 		for (auto i = mSeqFirst; nullptr != i; i = i->next)
  160. 		{
  161. 			std::cout << i->id << " ";
  162. 		}
  163. 	}
  164. private:
  165. 	std::shared_ptr<Item> mSeqFirst;
  166. 	std::shared_ptr<Item> mSeqLast;
  167.  
  168. 	std::array<std::shared_ptr<Level>, 100> mLevels;
  169. };
  170.  
  171. int main()
  172. {
  173. 	//std::fstream input("input.txt");
  174. 	auto& input = std::cin;
  175.  
  176. 	int num;
  177. 	input >> num;
  178.  
  179. 	Sequence seq;
  180.  
  181. 	for (auto i = 0; i < num; ++i)
  182. 	{
  183. 		int ai;
  184. 		input >> ai;
  185.  
  186. 		seq.add(ai);
  187. 	}
  188.  
  189. 	seq.sort();
  190. 	seq.optimize();
  191. 	seq.print();
  192.  
  193. 	return 0;
  194. }
  195.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
8
1 2 3 4 5 4 3 4
stdout
copy 
1 2 4 4 4
https://ideone.com/NHkiT8
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!