oj.uz

Submission #249890

# Submission time Handle Problem Language Result Execution time Memory
249890 2020-07-16T10:14:59 Z WLZ Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 384 KB 
#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 if (!x[1] && x[3]) {
    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 if (!y[1] && y[3]) {
    y_0 += m;
  }
  cout << "solution " << x_0 << ' ' << y_0 << endl;
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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