fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<algorithm>
  5. using namespace std;
  6. vector<pair<int, int>>vec; int n; bool used[210];
  7. map<long long, int>M;
  8. long long useds() {
  9. 	long long ret = 0, I = 1;
  10. 	for (int i = 0; i < n; i++) {
  11. 		ret += I*used[i]; I *= 2;
  12. 		I %= 1145141919810893; ret %= 1145141919810893;
  13. 	}
  14. 	return ret;
  15. }
  16. int solve() {
  17. 	if (M[useds()] >= 1)return M[useds()] - 1;
  18. 	cout << "? ";
  19. 	for (int i = 0; i < n; i++) {
  20. 		if (used[i] == true)putchar(49); else putchar(48);
  21. 	}
  22. 	cout << endl;
  23. 	int r = 0; cin >> r;
  24. 	M[useds()] = r + 1;
  25. 	return r;
  26. }
  27. void Zen_Re_Kkyo(int a1, int a2, int a3, int a4) {
  28. 	for (int i = a1; i < a2; i++) {
  29. 		for (int j = a3; j < a4; j++) {
  30. 			for (int k = 0; k < n; k++)used[k] = false; used[i] = true; used[j] = true;
  31. 			if (solve() >= 1)vec.push_back(make_pair(i, j));
  32. 		}
  33. 	}
  34. }
  35. void solve_Range(int a1, int a2, int a3, int a4, int a5) {
  36. 	if (a1 == a2 - 1 && a3 == a4 - 1) {
  37. 		vec.push_back(make_pair(a1, a3)); return;
  38. 	}
  39. 	if ((a2 - a1) < (a4 - a3)) {
  40. 		int Range = a4 - a3; Range /= 2;
  41. 		for (int j = 0; j < n; j++)used[j] = false;
  42. 		for (int j = a1; j < a2; j++)used[j] = true; for (int j = a3; j < a3 + Range; j++)used[j] = true;
  43. 		int E = solve();
  44. 		if (E >= 1)solve_Range(a1, a2, a3, a3 + Range, E);
  45. 		if (a5 - E >= 1)solve_Range(a1, a2, a3 + Range, a4, a5 - E);
  46. 	}
  47. 	else {
  48. 		int Range = a2 - a1; Range /= 2;
  49. 		for (int j = 0; j < n; j++)used[j] = false;
  50. 		for (int j = a1; j < a1 + Range; j++)used[j] = true; for (int j = a3; j < a4; j++)used[j] = true;
  51. 		int E = solve();
  52. 		if (E >= 1)solve_Range(a1, a1 + Range, a3, a4, E);
  53. 		if (a5 - E >= 1) solve_Range(a1 + Range, a2, a3, a4, a5 - E);
  54. 	}
  55. }
  56. void used_Range(int a1, int a2, int a3, int a4) {
  57. 	for (int i = 0; i < n; i++)used[i] = false;
  58. 	for (int i = a1; i < a2; i++)used[i] = true;
  59. 	for (int i = a3; i < a4; i++)used[i] = true;
  60. }
  61. void solve8(int i, int j, int T, int U) {
  62. 	if (T == 2) {
  63. 		Zen_Re_Kkyo(i, i + T, j, j + T);
  64. 		return;
  65. 	}
  66. 	if (T > U) {
  67. 		int E1, E2, E3;
  68. 		used_Range(i, i + T / 2, j, j + U); E1 = solve();
  69. 		used_Range(i, i + T / 2, j, j); E2 = solve(); E1 -= E2;
  70. 		used_Range(i, i, j, j + U); E3 = solve(); E1 -= E3;
  71. 		if (E1 >= 1) {
  72. 			if ((E1 >= 1 && E1 <= 3) && E2 == 0 && E3 == 0)solve_Range(i, i + T / 2, j, j + U, E1);
  73. 			else solve8(i, j, T / 2, U);
  74. 		}
  75. 		used_Range(i + T / 2, i + T, j, j + U); E1 = solve();
  76. 		used_Range(i + T / 2, i + T, j, j); E2 = solve(); E1 -= E2;
  77. 		used_Range(i, i, j, j + U); E3 = solve(); E1 -= E3;
  78. 		if (E1 >= 1) {
  79. 			if ((E1 >= 1 && E1 <= 3) && E2 == 0 && E3 == 0)solve_Range(i + T / 2, i + T, j, j + U, E1);
  80. 			else solve8(i + T / 2, j, T / 2, U);
  81. 		}
  82. 	}
  83. 	else {
  84. 		int E1, E2, E3;
  85. 		used_Range(i, i + T, j, j + U / 2); E1 = solve();
  86. 		used_Range(i, i + T, j, j); E2 = solve(); E1 -= E2;
  87. 		used_Range(i, i, j, j + U / 2); E3 = solve(); E1 -= E3;
  88. 		if (E1 >= 1) {
  89. 			if ((E1 >= 1 && E1 <= 3) && E2 == 0 && E3 == 0)solve_Range(i, i + T, j, j + U / 2, E1);
  90. 			else solve8(i, j, T, U / 2);
  91. 		}
  92. 		used_Range(i, i + T, j + U / 2, j + U); E1 = solve();
  93. 		used_Range(i, i + T, j, j); E2 = solve(); E1 -= E2;
  94. 		used_Range(i, i, j + U / 2, j + U); E3 = solve(); E1 -= E3;
  95. 		if (E1 >= 1) {
  96. 			if ((E1 >= 1 && E1 <= 3) && E2 == 0 && E3 == 0)solve_Range(i, i + T, j + U / 2, j + U, E1);
  97. 			else solve8(i, j + U / 2, T, U / 2);
  98. 		}
  99. 	}
  100. }
  101. void search() {
  102. 	int T = 8;
  103. 	for (int i = 0; i < n; i += T) {
  104. 		for (int j = 0; j < n; j++)used[j] = false; for (int j = i; j < i + T; j++)used[j] = true;
  105. 		int p1 = solve();
  106. 		if (p1 >= 1) {
  107. 			used_Range(i, i + T / 2, 0, 0); int E1 = solve();
  108. 			used_Range(i + T / 2, i + T, 0, 0); int E2 = solve();
  109.  
  110. 			if (p1 - E1 - E2 >= 1)solve8(i, i + T / 2, T / 2, T / 2);
  111. 			if (E1 >= 1) {
  112. 				for (int j = i; j < i + T / 2; j++) {
  113. 					for (int k = j + 1; k < i + T / 2; k++) {
  114. 						for (int l = 0; l < n; l++)used[l] = false; used[j] = true; used[k] = true;
  115. 						if (solve() >= 1)vec.push_back(make_pair(j, k));
  116. 					}
  117. 				}
  118. 			}
  119. 			if (E2 >= 1) {
  120. 				for (int j = i + T / 2; j < i + T; j++) {
  121. 					for (int k = j + 1; k < i + T; k++) {
  122. 						for (int l = 0; l < n; l++)used[l] = false; used[j] = true; used[k] = true;
  123. 						if (solve() >= 1)vec.push_back(make_pair(j, k));
  124. 					}
  125. 				}
  126. 			}
  127. 		}
  128. 	}
  129. 	for (int i = 0; i < n; i += T) {
  130. 		for (int j = i + T; j < n; j += T) {
  131. 			for (int k = 0; k < n; k++)used[k] = false;
  132. 			for (int k = i; k < i + T; k++)used[k] = true; for (int k = j; k < j + T; k++)used[k] = true;
  133. 			int p2 = solve();
  134. 			for (int k = 0; k < n; k++)used[k] = false; for (int k = i; k < i + T; k++)used[k] = true;
  135. 			int p1 = solve(); p2 -= p1;
  136. 			for (int k = 0; k < n; k++)used[k] = false; for (int k = j; k < j + T; k++)used[k] = true;
  137. 			int p3 = solve(); p2 -= p3;
  138. 			if ((p2 >= 1 && p2 <= 3) && p1 == 0 && p3 == 0) {
  139. 				solve_Range(i, i + T, j, j + T, p2);
  140. 			}
  141. 			else if (p2 >= 1) {
  142. 				solve8(i, j, T, T);
  143. 			}
  144. 		}
  145. 	}
  146. }
  147. int main() {
  148. 	cin >> n;
  149. 	search();
  150. 	sort(vec.begin(), vec.end());
  151. 	cout << "! ";
  152. 	for (int i = 0; i < vec.size(); i++) {
  153. 		if (i)cout << ' ';
  154. 		cout << "(" << vec[i].first << ',' << vec[i].second << ")";
  155. 	}
  156. 	cout << endl;
  157. 	return 0;
  158. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
!
https://ideone.com/jM7sw2
language:
C++14 (gcc 8.3)
created:
7 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!