Submission #1009131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009131		ALTAKEXE	Aliens (IOI07_aliens)	C++17	80 / 100	2 ms	600 KiB

aliens

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
const int MOD = 1e9 + 7;
using namespace std;
bool device(int a, int b)
{
  cout << "examine " << a << " " << b << endl;
  string res;
  cin >> res;
  return (res == "true");
}
int main()
{
  int n, X, Y;
  cin >> n >> X >> Y;
  int l, r, b;
  int low = X, high = n;
  for (int i = 0; X + (1 << i) <= n; i++)
  {
    int nx = X + (1 << i);
    if (!device(nx, Y))
    {
      high = nx;
      if (i != 0)
      {
        low = X + (1 << (i - 1));
      }
      break;
    }
  }
  while (high > low)
  {
    int mid = (high + low + 1) / 2;
    if (device(mid, Y))
      low = mid;
    else
      high = mid - 1;
  }
  r = low;
  low = 1, high = X;
  for (int i = 0; X - (1 << i) > 0; i++)
  {
    signed nx = X - (1 << i);
    if (!device(nx, Y))
    {
      low = nx;
      if (i != 0)
      {
        high = X - (1 << (i - 1));
      }
      break;
    }
  }
  while (high > low)
  {
    signed mid = (high + low) / 2;
    if (device(mid, Y))
      high = mid;
    else
      low = mid + 1;
  }
  l = low;
  low = 1, high = Y;
  for (int i = 0; Y - (1 << i) > 0; i++)
  {
    signed ny = Y - (1 << i);
    if (!device(X, ny))
    {
      low = ny;
      if (i != 0)
      {
        high = Y - (1 << (i - 1));
      }
      break;
    }
  }
  while (high > low)
  {
    signed mid = (high + low) / 2;
    if (device(X, mid))
      high = mid;
    else
      low = mid + 1;
  }
  b = low;
  signed cx = (l + r) / 2, cy = b + (r - l) / 2;
  int m = r - l + 1;
  int x1 = 0, x2 = 0;
  for (int i = 1; i <= 4; i++)
  {
    signed qx = cx - 2 * m * i;
    if (qx < 1)
      break;
    if (device(qx, cy))
      x1++;
    else
      break;
  }
  for (int i = 1; i <= 4; i++)
  {
    signed qx = cx + 2 * m * i;
    if (qx > n)
      break;
    if (device(qx, cy))
      x2++;
    else
      break;
  }
  int y1 = 0, y2 = 0;
  for (int i = 1; i <= 4; i++)
  {
    int qy = cy - 2 * m * i;
    if (qy < 1)
      break;
    if (device(cx, qy))
      y1++;
    else
      break;
  }
  for (int i = 1; i <= 4; i++)
  {
    int qy = cy + 2 * m * i;
    if (qy > n)
      break;
    if (device(cx, qy))
      y2++;
    else
      break;
  }
  cx += m * (x2 - x1);
  cy += m * (y2 - y1);
  cout << "solution " << cx << " " << cy << endl;
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10