Submission #249884

#	Time	Username	Problem	Language	Result	Execution time	Memory
249884		WLZ	Aliens (IOI07_aliens)	C++14	20 / 100	2 ms	384 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

bool examine(int x, int y) {
  cout << "examine " << x << ' ' << y << endl;
  string s;
  cin >> s;
  return (s == "true");
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, x_0, y_0;
  cin >> n >> x_0 >> y_0;
  long long x_r = n, y_r = n, x_l = 1;
  int k = 0;
  while (x_0 + (1ll << k) <= n && examine(x_0 + (1ll << k), y_0)) {
    k++;
  }
  long long lo = x_0, hi = min(n, x_0 + (1ll << k));
  while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;
    if (examine(mid, y_0)) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  x_r = lo;
  k = 0;
  while (y_0 + (1ll << k) <= n && examine(x_0, y_0 + (1ll << k))) {
    k++;
  }
  lo = y_0, hi = min(n, y_0 + (1ll << k));
  while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;
    if (examine(x_0, mid)) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  y_r = lo;
  k = 0;
  while (x_0 - (1ll << k) > 0 && examine(x_0 - (1ll << k), y_0)) {
    k++;
  }
  lo = max(1ll, x_0 - (1ll << k)), hi = x_0;
  while (lo < hi) {
    long long mid = (lo + hi) / 2;
    if (examine(mid, y_0)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  x_l = lo;
  long long m = x_r - x_l + 1;
  x_0 = x_r - (m - 1) / 2;
  y_0 = y_r - (m - 1) / 2;
  vector<bool> x(5, false);
  for (int i = -2; i <= 2; i++) {
    if (x_0 + 2 * i * m < 1 || x_0 + 2 * i * m > n) {
      continue;
    }
    x[i + 2] = examine(x_0 + 2 * i * m, y_0);
  }
  vector<bool> y(5, false);
  for (int i = -2; i <= 2; i++) {
    if (y_0 + 2 * i * m < 1 || y_0 + 2 * i * m > n) {
      continue;
    }
    y[i + 2] = examine(x_0, y_0 + 2 * i * m);
  }
  if (x[3] && x[4]) {
    x_0 += 2 * m;
  } else if (x[0] && x[1]) {
    x_0 -= 2 * m;
  } else if (x[1] && !x[3]) {
    x_0 -= m;
  } else {
    x_0 += m;
  }
  if (y[3] && y[4]) {
    y_0 += 2 * m;
  } else if (y[0] && y[1]) {
    y_0 -= 2 * m;
  } else if (y[1] && !y[3]) {
    y_0 -= m;
  } else {
    y_0 += m;
  }
  cout << "solution " << x_0 << ' ' << y_0 << endl;
  return 0;
}

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