oj.uz

Submission #1009132

# Submission time Handle Problem Language Result Execution time Memory
1009132 2024-06-27T09:11:26 Z ALTAKEXE Aliens (IOI07_aliens) C++17
80 / 100
 2 ms 436 KB 
#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++)
  {
    int nx = X - (1 << i);
    if (!device(nx, Y))
    {
      low = nx;
      if (i != 0)
      {
        high = X - (1 << (i - 1));
      }
      break;
    }
  }
  while (high > low)
  {
    int 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++)
  {
    int ny = Y - (1 << i);
    if (!device(X, ny))
    {
      low = ny;
      if (i != 0)
      {
        high = Y - (1 << (i - 1));
      }
      break;
    }
  }
  while (high > low)
  {
    int mid = (high + low) / 2;
    if (device(X, mid))
      high = mid;
    else
      low = mid + 1;
  }
  b = low;
  int 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++)
  {
    int qx = cx - 2 * m * i;
    if (qx < 1)
      break;
    if (device(qx, cy))
      x1++;
    else
      break;
  }
  for (int i = 1; i <= 4; i++)
  {
    int 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 2 ms 436 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 2 ms 344 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -