fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXL = 128;
  5. const int Q = 850;
  6.  
  7. int main() {
  8. 	ios::sync_with_stdio(0), cin.tie(0);
  9. 	const string chars = 
  10. 		"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  11. 		"abcdefghijklmnopqrstuvwxyz"
  12. 		"0123456789";
  13. 	assert(chars.size() == 62);
  14.  
  15. 	const bool testing = true;
  16. 	string test_ans;
  17. 	if (testing) {
  18. 		mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  19. 		//int L = uniform_int_distribution<int>(1, MAXL)(mt);
  20. 		int L = MAXL-1;
  21. 		for (int i = 0; i < L; i++) {
  22. 			test_ans += chars[uniform_int_distribution<int>(0, 61)(mt)];
  23. 		}
  24. 	}
  25. 	int query_cnt = 0;
  26. 	auto query = [&](string q) -> int {
  27. 		query_cnt++;
  28. 		cout << '?' << ' ' << q << '\n' << flush;
  29. 		int v;
  30. 		cin >> v;
  31. 		return v;
  32. 	};
  33. 	auto get_cnt = [&](char c) -> int {
  34. 		if (testing) {
  35. 			query_cnt++;
  36. 			int res = 0;
  37. 			for (char v : test_ans) {
  38. 				res += v == c;
  39. 			}
  40. 			return res;
  41. 		}
  42. 		return MAXL - query(string(MAXL, c));
  43. 	};
  44. 	vector<int> cnts(62);
  45. 	int L = 0;
  46. 	for (int i = 0; i < 62; i++) {
  47. 		cnts[i] = get_cnt(chars[i]);
  48. 		L += cnts[i];
  49. 	}
  50. 	auto is_subseq = [&](string q) -> int {
  51. 		assert(int(q.size()) <= L);
  52. 		if (testing) {
  53. 			query_cnt++;
  54. 			int i = 0;
  55. 			for (char c : test_ans) {
  56. 				if (c == q[i]) {
  57. 					i++;
  58. 					if (i == int(q.size())) return true;
  59. 				}
  60. 			}
  61. 			return false;
  62. 		} else {
  63. 			return query(q) == L - int(q.size());
  64. 		}
  65. 	};
  66. 	auto combine = [&](const string& a, const string& b) -> string {
  67. 		string res;
  68. 		int ia = 0, ib = 0;
  69. 		while (ia < int(a.size()) && ib < int(b.size())) {
  70. 			if (is_subseq(a.substr(0, ia+1) + b.substr(ib))) {
  71. 				res += a[ia++];
  72. 			} else {
  73. 				res += b[ib++];
  74. 			}
  75. 		}
  76. 		while (ia < int(a.size())) res += a[ia++];
  77. 		while (ib < int(b.size())) res += b[ib++];
  78. 		return res;
  79. 	};
  80. 	function<string(int , int)> solve = [&](int lx, int rx) {
  81. 		if (lx + 1 == rx) {
  82. 			return string(cnts[lx], chars[lx]);
  83. 		} else {
  84. 			return combine(solve(lx, (lx + rx) / 2), solve((lx + rx) / 2, rx));
  85. 		}
  86. 	};
  87. 	string ans = solve(0, 62);
  88. 	assert(query_cnt <= Q);
  89. 	if (testing) {
  90. 		assert(ans == test_ans);
  91. 	}
  92. 	cout << '!' << ' ' << ans << '\n';
  93. }
  94.  
  95.  
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
! 3FsE6pZhmI6eFtxfNZlBfSozYKmu0EJoehRu2e7Xg3qso227PaMpp32uRfgarc0fcglNyNEtShUqZKOMMJhp3icbJyVU2tnfUrPjbg5G5EdjrWZ4Uq9PQLJgtFwAucd
https://ideone.com/ySkISc
language:
C++14 (gcc 8.3)
created:
5 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!