fork download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1001;
  5.  
  6. int V;
  7. int row, col;
  8. int A[MAX][MAX];
  9. int row_type[MAX], col_type[MAX];
  10.  
  11. void Ask(int x, int y) {
  12. 	if (A[x][y]) {
  13. 		return;
  14. 	}
  15. 	printf("1 %d %d\n", x, y);
  16. 	fflush(stdout);
  17. 	scanf("%d", &A[x][y]);
  18. 	if (A[x][y] == V) {
  19. 		// Solution found.
  20. 		printf("2 %d %d\n", x, y);
  21. 		exit(0);
  22. 	}
  23. }
  24.  
  25. void SolveSubRectangle(int i1, int j1, int i2, int j2) {
  26. 	// The sub-rectangle has a special property. All rows are either increasing
  27. 	// or decreasing. Similarly, all columns are increasing or decreasing. For
  28. 	// details see the fucntions which call them and see the condition when it
  29. 	// was called.
  30. 	// Using the above property, ask atmost "n" questions to find if "V" exists
  31. 	// in this sub-rectangle.
  32. 	// The general strategy is to always ask the value present at almost
  33. 	// greatest cell. This almost greatest cell should have the property that we
  34. 	// can either eliminate a complete row or column after looking at this value.
  35. 	// This will help us perform atmost "n" queries. For details, refer to the
  36. 	// explanation of first case below. Others follow similarly. We know that
  37. 	// the its index as the sorting order of rows and columns is known. If that
  38. 	// value is less than "V", we either increase/decrease only row or column
  39. 	// index or we increase/decrease both the index of row and column. If at any
  40. 	// moment the indices are out of bounds of the subrectangle we exit.
  41. 	int i, j;
  42. 	if (row_type[i1] == 1) {
  43. 		if (col_type[j2] == 1) {
  44. 			// All rows and columns are increasing.
  45. 			// We start with cell (i1, j2). If this cell is greater than "V",
  46. 			// then we need to go to previous column as rows are increasing.
  47. 			// If this value was smaller we must go to next row as columns are
  48. 			// increasing. We should also try to increase the column index if
  49. 			// possible as it will help us eliminate that full column or row in
  50. 			// next iteration.
  51. 			i = i1; j = j2;
  52. 			while (i <= i2) {
  53. 				Ask(i, j);
  54. 				if (V < A[i][j]) {
  55. 					if (--j < j1) return;
  56. 				} else {
  57. 					if (j < j2) j++;
  58. 					if (++i > i2) return;
  59. 				}
  60. 			}
  61. 		} else {
  62. 			// All rows are increasing and columns are decreasing.
  63. 			i = i2; j = j2;
  64. 			while (i >= i1) {
  65. 				Ask(i, j);
  66. 				if (V < A[i][j]) {
  67. 					if (--j < j1) return;
  68. 				} else {
  69. 					if (j < j2) j++;
  70. 					if (--i < i1) return;
  71. 				}
  72. 			}
  73. 		}
  74. 	} else {
  75. 		if (col_type[j2] == 1) {
  76. 			// All rows are increasing and columns are decreasing.
  77. 			i = i1; j = j1;
  78. 			while (i <= i2) {
  79. 				Ask(i, j);
  80. 				if (V < A[i][j]) {
  81. 					if (++j > j2) return;
  82. 				} else {
  83. 					if (j > j1) j--;
  84. 					if (++i > i2) return;
  85. 				}
  86. 			}
  87. 		} else {
  88. 			// All rows and columns are decreasing.
  89. 			i = i2; j = j1;
  90. 			while (i >= i1) {
  91. 				Ask(i, j);
  92. 				if (V < A[i][j]) {
  93. 					if (++j > j2) return;
  94. 				} else {
  95. 					if (j > j1) j--;
  96. 					if (--i < i1) return;
  97. 				}
  98. 			}
  99. 		}
  100. 	}
  101. }
  102.  
  103. void Resi2x2AA(int n, int i1, int j1) {
  104. 	// Find subrectangles to ignore and what to query for solution.
  105. 	// Refer to editorial images for how to ignore subrectangles.
  106. 	int i, j;
  107. 	int can[2][2] = {{1,1},{1,1}};
  108. 	if (V > A[i1-1][j1-1]) {
  109. 		can[0][0] = 0;
  110. 	} else {
  111. 		can[0][1] = can[1][0] = 0;
  112. 	}
  113. 	if (V > A[i1][j1]) {
  114. 		can[1][1] = 0;
  115. 	} else {
  116. 		can[0][1] = can[1][0] = 0;
  117. 	}
  118. 	if (can[0][0]) {
  119. 		SolveSubRectangle(1, 1, i1-1, j1-1);
  120. 	}
  121. 	if (can[0][1]) {
  122. 		SolveSubRectangle(1, j1, i1-1, n);
  123. 	}
  124. 	if (can[1][0]) {
  125. 		SolveSubRectangle(i1, 1, n, j1-1);
  126. 	}
  127. 	if (can[1][1]) {
  128. 		SolveSubRectangle(i1, j1, n, n);
  129. 	}
  130. }
  131.  
  132.  
  133. void Resi2x2BB(int n, int i1, int j1) {
  134. 	// Find subrectangles to ignore and what to query for solution.
  135. 	// Refer to editorial images for how to ignore subrectangles.
  136. 	int i, j;
  137. 	int can[2][2] = {{1,1},{1,1}};
  138. 	if (V < A[i1-1][j1-1]) {
  139. 		can[0][0] = 0;
  140. 	} else {
  141. 		can[0][1] = can[1][0] = 0;
  142. 	}
  143. 	if (V < A[i1][j1]) {
  144. 		can[1][1] = 0;
  145. 	} else {
  146. 		can[0][1] = can[1][0] = 0;
  147. 	}
  148. 	if (can[0][0]) {
  149. 		SolveSubRectangle(1, 1, i1-1, j1-1);
  150. 	}
  151. 	if (can[0][1]) {
  152. 		SolveSubRectangle(1, j1, i1-1, n);
  153. 	}
  154. 	if (can[1][0]) {
  155. 		SolveSubRectangle(i1, 1, n, j1-1);
  156. 	}
  157. 	if (can[1][1]) {
  158. 		SolveSubRectangle(i1, j1, n, n);
  159. 	}
  160. }
  161.  
  162. void Resi2x2(int n) {
  163. 	// Find the value at the 4 most important points i.e where rows and
  164. 	// columns change their type.
  165. 	int i, j, i1, j1, i2, j2;
  166. 	i1 = 1; j1 = 1;
  167. 	while (row_type[i1] == row_type[1]) i1++;
  168. 	while (col_type[j1] == col_type[1]) j1++;
  169. 	// Rows partition: [1, i1-1] and [i1, n]
  170. 	// Columns partition: [1, j1-1] and [j1, n]
  171. 	for(int x=i1; x<=n; ++x) {
  172. 		assert(row_type[i1] == row_type[x]);
  173. 	}
  174. 	for(int y=j1; y<=n; ++y) {
  175. 		assert(col_type[j1] == col_type[y]);
  176. 	}
  177. 	Ask(i1-1, j1-1);
  178. 	Ask(i1-1, j1);
  179. 	Ask(i1, j1-1);
  180. 	Ask(i1, j1);
  181. 	if ((row_type[1] == 1) && (col_type[1] == 1)) {
  182. 		Resi2x2AA(n, i1, j1);
  183. 	}
  184. 	if ((row_type[1] == -1) && (col_type[1] == -1)) {
  185. 		Resi2x2BB(n, i1, j1);
  186. 	}
  187. }
  188.  
  189. void SolveColumn(int n) {
  190. 	// Ask atmost "n" queries to identify which sub-rectangle is a possible
  191. 	// candidate to contain "V".
  192. 	// Worst case: rows are alternating increasing and decreasing or vice-versa.
  193. 	int found = 0;
  194. 	int i, j, i1, i2;
  195. 	i2 = 1;
  196. 	while (i2 <= n) {
  197. 		i1 = i2;
  198. 		while ((i2 <= n) && (row_type[i2] == row_type[i1])) i2++;
  199. 		// All rows from [i1, i2-1] are either inncreasing or decreasing.
  200. 		// Based on whether rows are increasing or decreasing, select the column
  201. 		// which will have the maximum element for every row. It can be
  202. 		// either row "1" or "n". If for that column and row range, the
  203. 		// numbers have "V" in their range, we have found a valid sub-rectangle
  204. 		// which is the possible candidate to contain "V". Note that since we
  205. 		// are iterating over rows in increasing order and not doing a binary
  206. 		// search. So, if the previous rows were ignored, it means their value
  207. 		// was either less or greater than "V". So, only the other condition is
  208. 		// required to be checked.
  209. 		if (col_type[1] == 1) {
  210. 			// All columns are increasing.
  211. 			if (row_type[i1] == -1) {
  212. 				// Current set of rows are decreasing.
  213. 				Ask(i2-1, 1);
  214. 				if (V <= A[i2-1][1]) {
  215. 					found = 1; break;
  216. 				}
  217. 			} else {
  218. 				// Current set of rows are increasing.
  219. 				Ask(i2-1, n);
  220. 				if (V <= A[i2-1][n]) {
  221. 					found = 1; break;
  222. 				}
  223. 			}
  224. 		} else {
  225. 			// All columns are decreasing.
  226. 			if (row_type[i1] == -1) {
  227. 				// Current set of rows are decreasing.
  228. 				Ask(i2-1, n);
  229. 				if (V >= A[i2-1][n]) {
  230. 					found = 1; break;
  231. 				}
  232. 			} else {
  233. 				// Current set of rows are increasing.
  234. 				Ask(i2-1, 1);
  235. 				if (V >= A[i2-1][1]) {
  236. 					found = 1; break;
  237. 				}
  238. 			}
  239. 		}
  240. 	}
  241. 	if (found) {
  242. 		// "i2" is decremented as the valid range was [i1, i2-1] as explained
  243. 		// before.
  244. 		i2--;
  245. 		SolveSubRectangle(i1, 1, i2, n);
  246. 	}
  247. }
  248.  
  249. void SolveRow(int n) {
  250. 	// Ask atmost "n" queries to identify which sub-rectangle is a possible
  251. 	// candidate to contain "V".
  252. 	// Worst case: columns are alternating increasing or decreasing or
  253. 	// vice-versa.
  254. 	int found = 0;
  255. 	int i, j, j1, j2;
  256. 	j2 = 1;
  257. 	while (j2 <= n) {
  258. 		j1 = j2;
  259. 		while ((j2 <= n) && (col_type[j2] == col_type[j1])) j2++;
  260. 		// All columns are [j1, j2-1] are either increasing or decreasing.
  261. 		// Based on whether columns are increasing or decreasing, select the row
  262. 		// which will have the maximum element for every column. It can be
  263. 		// either column "1" or "n". If for that row and column range, the
  264. 		// numbers have "V" in their range, we have found a valid sub-rectangle
  265. 		// which is the possible candidate to contain "V". Note that since we
  266. 		// are iterating over columns in increasing order and not doing a binary
  267. 		// search. So, if the previous columns were ignored, it means their value
  268. 		// was either less or greater than "V". So, only the other condition is
  269. 		// required to be checked.
  270. 		if (row_type[1] == 1) {
  271. 			// All rows are increasing.
  272. 			if (col_type[j1] == -1) {
  273. 				// Current set of columns are decreasing.
  274. 				Ask(1, j2-1);
  275. 				if (V <= A[1][j2-1]) {
  276. 					found = 1; break;
  277. 				}
  278. 			} else {
  279. 				// Current set of columns are increasing.
  280. 				Ask(n, j2-1);
  281. 				if (V <= A[n][j2-1]) {
  282. 					found = 1; break;
  283. 				}
  284. 			}
  285. 		} else {
  286. 			// All rows are decreasing.
  287. 			if (col_type[j1] == -1) {
  288. 				// Current set of columns are decreasing.
  289. 				Ask(n, j2-1);
  290. 				if (V >= A[n][j2-1]) {
  291. 					found = 1; break;
  292. 				}
  293. 			} else {
  294. 				// Current set of columns are increasing.
  295. 				Ask(1, j2-1);
  296. 				if (V >= A[1][j2-1]) {
  297. 					found = 1; break;
  298. 				}
  299. 			}
  300. 		}
  301. 	}
  302. 	if (found) {
  303. 		// "j2" is decremented as the valid range was [j1, j2-1] as explained
  304. 		// before.
  305. 		j2--;
  306. 		SolveSubRectangle(1, j1, n, j2);
  307. 	}
  308. }
  309.  
  310.  
  311. void Solve(int n, int k) {
  312. 	// Ask "2n" queries to identify type of every row and column.
  313. 	// Use help of diagonal element and its neighbour.
  314. 	Ask(1, 1);
  315. 	Ask(1, 2);
  316. 	if (A[1][1] < A[1][2]) row_type[1] = 1; else row_type[1] = -1;
  317. 	for (int i = 2; i < n; i++) {
  318. 		Ask(i, i);
  319. 		Ask(i, i+1);
  320. 		if (A[i][i] < A[i][i+1]) row_type[i] = 1; else row_type[i] = -1;
  321. 		if (A[i-1][i] < A[i][i]) col_type[i] = 1; else col_type[i] = -1;
  322. 	}
  323. 	Ask(n, n);
  324. 	Ask(n, 1);
  325. 	if (A[n][1] < A[n][n])	row_type[n] = 1; else row_type[n] = -1;
  326. 	if (A[1][1] < A[n][1])	col_type[1] = 1; else col_type[1] = -1;
  327. 	if (A[n-1][n] < A[n][n]) col_type[n] = 1; else col_type[n] = -1;
  328. 	row = col = 0;
  329. 	for (int i = 2; i <= n; i++) {
  330. 		if (row_type[i-1] != row_type[i]) row++;
  331. 		if (col_type[i-1] != col_type[i]) col++;
  332. 	}
  333. 	if (row == 0) {
  334. 		// All rows are increasing or decreasing.
  335. 		SolveRow(n);
  336. 	} else if (col == 0) {
  337. 		// All columns are increasing or decreasing.
  338. 		SolveColumn(n);
  339. 	} else {
  340. 		// Initial set of rows are of one type and rest of another type.
  341. 		// Initial set of columns are one type and rest of another type.
  342. 		assert(row == 1);
  343. 		assert(col == 1);
  344. 		Resi2x2(n);
  345. 	}
  346. }
  347.  
  348. int main() {
  349. 	int n, k;
  350. 	scanf("%d%d%d",&n, &k, &V);
  351. 	Solve(n,k);
  352. 	printf("2 -1 -1\n");
  353. 	fflush(stdout);
  354. 	return 0;
  355. }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
3 10 4
2
6
9
12
13
7
8
4
stdout
copy 
1 1 1
1 1 2
1 2 2
1 2 3
1 3 3
1 3 1
1 1 3
1 2 1
2 2 1
https://ideone.com/5m6n4Q
language:
C++14 (gcc 8.3)
created:
5 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!