/**
* Solution to IOI 2009 problem "hill"
*
* We employ a divide and conquer algorithm, by scanning all cells on a
* line that cuts the area in half. For the highest cell in that line (call
* it X), we scan the cells on either side of the line adjacent to that
* cell. We now have a few cases:
*
* 1) All the cells surrounding X are of lower height. X is then a hill
* 2) At least one of the cells adjacent to X and not on the line is
* higher than X. If both cells are higher, then use the highest one;
* call the higher cell Y. Either Y is a hill, or there is another
* cell in the same half of the area as Y which is higher than it and
* is a hill.
*
* In the event of option 2, the area being scanned can be shrunk to the
* half in which Y lies, and the process repeated. The only minor thing
* that must be catered for, is the case where we scan a line and the
* highest adjacent cell lies in the half different to the globally best
* height in the whole area. In such cases, the other half should be
* recursed into, otherwise a true hill might not be found. Consider
* the following map:
*
* 18 7 9 10 5 3
* 12 6 8 11 4 2
* 17 13 12 14 15 16
*
* and suppose that we started by scanning the whole of the middle row.
* We would find that 12 is the highest cell, and scan the cells adjacent
* to it, with heights 17 and 18. Since 18 is the highest, we would recurse
* into the top portion of the map, meaning we are required to solve the
* sub-problem:
*
* 18 7 9 10 5 3
*
* We attack this problem by scanning the middle column, say the 9. Since
* it is the only cell in the column it is also the highest, and we scan
* the cells on either side, finding that 10 is higher. If we now recursed
* into the right half of this row, we would fail to find a hill -- since
* the 10 is actually bordered by an 11 below it. Instead, we must realise
* that although the 10 seems like it might be a hill, we have seen a higher
* value of 18 and must thus recurse to the left.
*
* Similarly, if we scanned the 10 as the middle column, we might be
* tempted to declare it a hill, as the 9 and 5 adjacent to it are both
* lower. Again, this is erroneous, and remedied by the fact that we have
* seen a higher cell which lies to the left of the 10.
*
* Carl Hultquist, chultquist@gmail.com
*/
#include
#include
using namespace std;
// We cache queries for efficiency, so that if our algorithm happens
// to query for a height more than once we don't actually issue the
// query.
int cache[1000][1000];
/**
* Query for the height at co-ordinates (x,y), where x and y are
* 0-indexed.
*/
long long query(int x, int y)
{
if (cache[x][y] == -1)
{
// We have not queried for this pair of co-ordinate yet, so find
// out what the height is and store it in the cache.
cout << "0 " << x + 1 << " " << y + 1 << endl;
cout.flush();
cin >> cache[x][y];
}
return cache[x][y];
}
/**
* Identifies a hill at the given co-ordinates and terminates the program.
*/
void identify_hill(int x, int y)
{
cout << "1 " << x + 1 << " " << y + 1 << endl;
cout.flush();
exit(0);
}
int main()
{
int n, m;
cin >> n >> m;
// Initialise the cache
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cache[i][j] = -1;
// Start by considering the whole area
int x1 = 0, x2 = n - 1, y1 = 0, y2 = m - 1;
// The greatest height and co-ordinates at which this height was
// observed.
int curBest = -1;
int bestX = -1, bestY = -1;
// Keep recursing until we have only a single cell left
while (x1 != x2 || y1 != y2)
{
int w = x2 - x1;
int h = y2 - y1;
// We split based on which dimension is greater, so as to eliminate
// a greater portion of the remaining area.
if (w > h)
{
// Divide along the height
int mid = (x1 + x2) / 2;
// Scan the column
int bestH = -1;
int by = -1;
for (int y = y1; y <= y2; y++)
{
int h = query(mid, y);
if (h > bestH)
{
bestH = h;
by = y;
}
}
// Check the adjacent cells to the highest cell in the
// column
int bx = mid;
if (mid > 0 && query(mid - 1, by) > bestH)
{
bestH = query(mid - 1, by);
bx = mid - 1;
}
if (mid < (n - 1) && query(mid + 1, by) > bestH)
{
bestH = query(mid + 1, by);
bx = mid + 1;
}
// If both adjacent cells are lower, and the height of
// this cell is greater than the best we have seen thus
// far, then this must be a hill.
if (bx == mid && bestH > curBest)
identify_hill(bx, by);
// If we have found a higher cell than any seen thus far,
// update our state.
if (bestH > curBest)
{
curBest = bestH;
bestX = bx;
bestY = by;
}
// Choose a half of the map to recurse into, always choosing
// the side with the highest cell seen thus far.
if (bestX > mid)
x1 = mid + 1;
else
x2 = mid - 1;
}
else
{
// Divide along the width
int mid = (y1 + y2) / 2;
// Scan the row
int bestH = -1;
int bx = -1;
for (int x = x1; x <= x2; x++)
{
int h = query(x, mid);
if (h > bestH)
{
bestH = h;
bx = x;
}
}
// Check the adjacent cells to the highest cell in the
// row
int by = mid;
if (mid > 0 && query(bx, mid - 1) > bestH)
{
bestH = query(bx, mid - 1);
by = mid - 1;
}
if (mid < (m - 1) && query(bx, mid + 1) > bestH)
{
bestH = query(bx, mid + 1);
by = mid + 1;
}
// If both adjacent cells are lower, and the height of
// this cell is greater than the best we have seen thus
// far, then this must be a hill.
if (by == mid && bestH > curBest)
identify_hill(bx, by);
// If we have found a higher cell than any seen thus far,
// update our state.
if (bestH > curBest)
{
curBest = bestH;
bestX = bx;
bestY = by;
}
// Choose a half of the map to recurse into, always choosing
// the side with the highest cell seen thus far.
if (bestY > mid)
y1 = mid + 1;
else
y2 = mid - 1;
}
}
// If we have narrowed our area down to a single cell, then this cell
// must be higher than any seen thus far and is thus a hill.
identify_hill(x1, y1);
return 0;
}