fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <fstream>
  4. #include <set>
  5. #include <vector>
  6. #include <cassert>
  7. #include <functional>
  8. using namespace std;
  9.  
  10. #define PRINT_PROGRESS
  11.  
  12. struct drug_info_t
  13. {
  14. 	char name[64];
  15. 	int require;
  16. 	int block[2];
  17. 	int effect[4];
  18. };
  19.  
  20. const drug_info_t input[] =
  21. {
  22. 	/* id      name          require  block      effect             */
  23. 	/*  0 */ {"<null>",      0,       {0,  0},   {+0,  +0,  +0,  +0 }},
  24. 	/*  1 */ {"AMPEA",       0,       {13, 0},   {+14  +7,  +15  +8 }},
  25. 	/*  2 */ {"BMA",         0,       {14, 22},  {+11, +15, +10, +16}},
  26. 	/*  3 */ {"DXAMPEA",     0,       {10, 23},  {+8,  +7,  +11, +11}},
  27. 	/*  4 */ {"TST",         0,       {17, 0},   {+7,  +13, +15, +9 }},
  28. 	/*  5 */ {"DHEA",        2,       {15, 0},   {+13, +12, +9,  +19}},
  29. 	/*  6 */ {"THG",         0,       {9,  20},  {+17, +17, +14, +8 }},
  30. 	/*  7 */ {"anadrol",     4,       {24, 0},   {+17, +14, +11, +14}},
  31. 	/*  8 */ {"EPO",         1,       {6,  0},   {+13, +0,  +0,  -2 }},
  32. 	/*  9 */ {"argoxin",     8,       {15, 0},   {+10, -1,  +0,  +0 }},
  33. 	/* 10 */ {"atomoxetin",  9,       {4,  19},  {+17, +0,  +0,  -4 }},
  34. 	/* 11 */ {"bolasteron",  0,       {16, 19},  {-1,  +11, +0,  -1 }},
  35. 	/* 12 */ {"bolandiol",   11,      {18, 0},   {-2,  +8,  +1,  -3 }},
  36. 	/* 13 */ {"calusteron",  12,      {21, 0},   {+0,  +10, +0,  -2 }},
  37. 	/* 14 */ {"danasol",     3,       {18, 0},   {-2,  +0,  +15, +2 }},
  38. 	/* 15 */ {"esiclen",     14,      {5,  0},   {-1,  +2,  +10, +3 }},
  39. 	/* 16 */ {"stanosolol",  15,      {23, 0},   {+0,  +0,  +9,  +5 }},
  40. 	/* 17 */ {"gonadorelin", 0,       {7,  0},   {+2,  +1,  -4,  +16}},
  41. 	/* 18 */ {"FGF",         17,      {16, 20},  {-5,  +1,  +3,  +8 }},
  42. 	/* 19 */ {"formoterol",  18,      {22, 0},   {+2,  +0,  +2,  +14}},
  43. 	/* 20 */ {"raloxiphen",  9,       {5,  0},   {+0,  +21, -15, -10}},
  44. 	/* 21 */ {"cyclophenil", 12,      {7,  0},   {+18, -19, +29, +20}},
  45. 	/* 22 */ {"AMPK",        20,      {2,  0},   {+22, +0,  -10, +32}},
  46. 	/* 23 */ {"albumin",     22,      {4,  0},   {-10, +24, +30, +6 }},
  47. 	/* 24 */ {"mannitol",    14,      {10, 0},   {+38, +24, +0,  -10}},
  48. 	/* 25 */ {"IGF-1",       23,      {19, 0},   {-10, +21, +28, +31}},
  49. };
  50. const int N = sizeof(input) / sizeof(drug_info_t);
  51.  
  52. using solution_t = array<int, N>;
  53.  
  54. int stats[4];
  55. short blocked[N];
  56. bool used[N] = {true};
  57. vector<int> cur;
  58. vector<solution_t> sol_list;
  59. int best_score;
  60.  
  61.  
  62. bool apply(int id)
  63. {
  64. 	auto const& d = input[id];
  65.  
  66. 	if (used[id] || blocked[id] || !used[d.require]) { return false; }
  67.  
  68. 	used[id] = true;
  69. 	++blocked[d.block[0]];
  70. 	++blocked[d.block[1]];
  71.  
  72. 	for (int i = 0; i < 4; ++i)
  73. 	{
  74. 		stats[i] += d.effect[i];
  75. 	}
  76.  
  77. 	cur.push_back(id);
  78.  
  79. 	return true;
  80. }
  81.  
  82. void cancel(int id)
  83. {
  84. 	auto const& d = input[id];
  85.  
  86. 	cur.pop_back();
  87.  
  88. 	for (int i = 0; i < 4; ++i)
  89. 	{
  90. 		stats[i] -= d.effect[i];
  91. 	}
  92.  
  93. 	--blocked[d.block[1]];
  94. 	--blocked[d.block[0]];
  95. 	used[id] = false;
  96. }
  97.  
  98. int score();
  99. void optimize()
  100. {
  101. 	int s = score();
  102. 	if (s > best_score)
  103.     {
  104.         sol_list.clear();
  105.     }
  106. 	if (s >= best_score)
  107. 	{
  108. 		sol_list.emplace_back();
  109. 		copy(cur.begin(), cur.end(), sol_list.back().begin());
  110. 		best_score = s;
  111. 	}
  112.  
  113. 	for (int id = 1; id < N; ++id)
  114. 	{
  115. #ifdef PRINT_PROGRESS
  116. 	    if (cur.empty())
  117.         {
  118.             cout << id << "/" << (N - 1);
  119.         }
  120.         else if (cur.size() == 1)
  121.         {
  122.             cout << ".";
  123.         }
  124. #endif
  125.  
  126. 		if (apply(id))
  127. 		{
  128. 			optimize();
  129. 			cancel(id);
  130. 		}
  131.  
  132. #ifdef PRINT_PROGRESS
  133. 		if (cur.empty())
  134.         {
  135.             cout << "\n";
  136.         }
  137. #endif
  138. 	}
  139. }
  140.  
  141. void print_solutions(ostream& os, bool first)
  142. {
  143.     for (auto const& s : sol_list)
  144. 	{
  145. 		for (int id : s)
  146. 		{
  147. 		    if (!id) { break; }
  148. 			os << input[id].name << " ";
  149. 			assert(apply(id));
  150. 		}
  151.  
  152. 		os << "\t[";
  153. 		for (int i = 0; i < 4; ++i)
  154. 		{
  155. 			if (i) { os << "\t"; }
  156. 			os << stats[i];
  157. 		}
  158. 		os << "]\n";
  159.  
  160. 		for (int id : s)
  161. 		{
  162. 		    if (!id) { break; }
  163. 			cancel(id);
  164. 		}
  165.  
  166. 		if (first) { break; }
  167. 	}
  168. }
  169.  
  170.  
  171. int score()
  172. {
  173. 	return stats[0] + stats[1] + stats[2] + stats[3];
  174. }
  175.  
  176. int main()
  177. {
  178.     sol_list.reserve(1024 * 1024);
  179. 	sol_list.emplace_back();
  180. 	best_score = score();
  181.  
  182. 	optimize();
  183.  
  184. //	ofstream os("out.txt");
  185. //	print_solutions(os, false);
  186.  
  187. 	print_solutions(cout, true);
  188. }
  189.  
Time limit exceeded #stdin #stdout 5s 9964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AhKc08
phantom doc
language:
C++14 (gcc 8.3)
created:
4 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!