oj.uz

Submission #998717

# Submission time Handle Problem Language Result Execution time Memory
998717 2024-06-14T14:49:56 Z espnINF Aliens (IOI07_aliens) C++17
100 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int examine(int X, int Y) {
  cout << "examine " << X << ' ' << Y << endl;
  string s;
  cin >> s;
  return (s == "true");
}
void solution(int XC, int YC) {
  cout << "solution " << XC << ' ' << YC << endl;
  exit(0);
}

ll m, n, x, y, a, b, c, d, l, r, mid, p, q, up, down, le, ri, length;
ll binsearch1(ll l, ll r, bool f) { // right or up, f = 1 --> y
  while (l <= r) {
    if (l == r) break;
    else if (l == r - 1) {
      if (examine((f == 0 ? r : x), (f == 0 ? y : r))) l = r;
      else r = l;
      break;
    }else {
      mid = (l + r) / 2;
      if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) r = mid;
      else l = mid;
    }
  }
  return l;
}
ll binsearch2(ll l, ll r, bool f) { // left or down
  while (l <= r) {
    if (l == r) break;
    else if (l == r - 1) {
      if (examine((f == 0 ? l : x), (f == 0 ? y : l))) r = l;
      else l = r;
      break;
    }else {
      mid = (l + r) / 2;
      if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) l = mid;
      else r = mid;
    }
  }
  return l;
}
#define so solution
void findCenter(ll N, ll X0, ll Y0) {
  up = 0, down = 0, le = 0, ri = 0;
  x = X0; y = Y0; n = N;
  bool t = 1;
  for (int i = 1; x <= n; i *= 2) {
    x += i;
    if (x - i == n) break;
    if (x > n) x=n;
    if (!examine(x, y)) {
      c = binsearch1(x - i, x, 0);
      t = 0;
      break;
    }
  }
  if (t) c = n;
  t = 1;
  x = X0;
  for (int i = 1; y <= n; i *= 2) {
    y += i;
    if (y - i == n) break;
    if (y > n) y=n;
    if (!examine(x, y)) {
      d = binsearch1(y - i, y, 1);
      t = 0;
      break;
    }
  }
  if (t) d = n;
  t = 1;
  y = Y0;
  for (int i = 1; x >= 1; i *= 2) {
    x -= i;
    if (x + i == 1) break;
    if (x < 1) x=1;
    if (!examine(x, y)) {
      a = binsearch2(x, x + i, 0);
      t = 0;
      break;
    }
  }
  if (t) a = 1;
  t = 1;
  x = X0;
  b = d - (c - a);
  length = c - a + 1;
  p = (a + c) / 2;
  q = (b + d) / 2;
  // left
  if (x - 2 * length >= 1) le += examine(x - 2 * length, y);
  if (x - 4 * length >= 1) le += examine(x - 4 * length, y);
  // up
  if (y + 2 * length <= n) up += examine(x, y + 2 * length);
  if (y + 4 * length <= n) up += examine(x, y + 4 * length);
  // down
  if (y - 2 * length >= 1) down += examine(x, y - 2 * length);
  if (y - 4 * length >= 1) down += examine(x, y - 4 * length);
 
  // 13 cases
  if (up == 0) {
    if (down == 2) {
      if (le == 0) so(p + 2 * length, q - 2 * length);
      else if (le == 1) so(p, q - 2 * length);
      else so(p - 2 * length, q - 2 * length);
    }else {
      if (le == 0) so(p + length, q - length);
      else so(p - length, q - length);
    }
  }else if (up == 1) {
    if (down == 1) {
      if (le == 0) so(p + 2 * length, q);
      else if (le == 1) so(p, q);
      else so(p - 2 * length, q);
    }else {
      if (le == 0) so(p + length, q + length);
      else so(p - length, q + length);
    }
  }else {
    if (le == 0) so(p + 2 * length, q + 2 * length);
    else if (le == 1) so(p, q + 2 * length);
    else so(p - 2 * length, q + 2 * length);
  }
  return;
}
// binsearch so annoying
int main() {
  ll n, x, y;
  cin >> n >> x >> y;
  findCenter(n, x, y);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 1 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 0 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 0 ms 344 KB Output is correct

Subtask #6
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 #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 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 #9
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 #10
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