fork(16) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <string>
  5. #include <algorithm>
  6. #include <cctype>
  7. #include <iterator>
  8. #include <functional>
  9. #include <ctime>
  10. using namespace std;
  11.  
  12. const int INVALID = -1;
  13.  
  14. const vector<string> elem_names{
  15. 	"H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al",
  16. 	"Si", "P", "S", "Cl", "Ar", "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe",
  17. 	"Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y",
  18. 	"Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb",
  19. 	"Te", "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd",
  20. 	"Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir",
  21. 	"Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn", "Fr", "Ra", "Ac",
  22. 	"Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm", "Md", "No",
  23. 	"Lr", "Rf", "Db", "Sg", "Bh", "Hs", "Mt", "Ds", "Rg", "Cn", "Nh", "Fl",
  24. 	"Mc", "Lv", "Ts", "Og"
  25. };
  26.  
  27. unordered_map<string, int> elem;
  28.  
  29. void spell(string const & s) {
  30. 	const int q = s.size();
  31. 	vector<int> has_repr(q + 1);
  32. 	vector<vector<int>> repr(q + 1, vector<int>(3, INVALID));
  33. 	has_repr[0] = true;
  34. 	for (int i = 0; i <= q; ++i) {
  35. 		if (!has_repr[i]) continue;
  36. 		for (int j = 1; j <= 3; ++j) {
  37. 			if (i + j > q) break;
  38. 			auto iter = elem.find(s.substr(i, j));
  39. 			if (iter != end(elem)) {
  40. 				has_repr[i + j] = true;
  41. 				repr[i + j][j - 1] = iter->second;
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	string out = s;
  47. 	function<void(int)> dfs = [&](int i) {
  48. 		if (!has_repr[i]) {
  49. 			return;
  50. 		}
  51. 		if (!i) {
  52. 			cout << out << '\n';
  53. 			return;
  54. 		}
  55. 		for (int j = 1; j <= 3; ++j) {
  56. 			int r = repr[i][j - 1];
  57. 			if (r == INVALID) continue;
  58. 			const string & name = elem_names[r];
  59. 			copy(begin(name), end(name), begin(out) + i - j);
  60. 			dfs(i - j);
  61. 		}
  62. 	};
  63.  
  64. 	dfs(q);
  65. }
  66.  
  67. int main() {
  68. 	for (int i = 0, ilen = elem_names.size(); i < ilen; ++i) {
  69. 		string s = elem_names[i];
  70. 		s[0] = tolower(s[0]);
  71. 		elem[s] = i;
  72. 	}
  73.  
  74. 	spell("amputation");
  75.  
  76. 	std::cout.setstate(std::ios_base::badbit);
  77.  
  78. 	clock_t tStart = clock();
  79.  
  80. 	for (int i = 0; i < 456976; ++i) {
  81. 		int ii = i;
  82. 		string s;
  83. 		for (int j = 0; j < 4; ++j) {
  84. 			s += 'a' + ii % 26;
  85. 			ii /= 26;
  86. 		}
  87. 		spell(s);
  88. 	}
  89.  
  90. 	cout.clear();
  91. 	cout << double(clock() - tStart) / CLOCKS_PER_SEC << endl;
  92. }
Success #stdin #stdout 0.26s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
AmPUTaTiON
AmPuTaTiON
0.260222
https://ideone.com/iVpeu3
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!