Submission #966567

#	Time	Username	Problem	Language	Result	Execution time	Memory
966567		kilkuwu	Aliens (IOI07_aliens)	C++17	60 / 100	2 ms	600 KiB

aliens

#include <bits/stdc++.h>

#define nl '\n'

long long N;
std::array<long long, 2> P0;
long long ask(std::array<long long, 2> P) {
  auto [x, y] = P;
  assert(1 <= x && x <= N && 1 <= y && y <= N);
  std::cout << "examine " << x << " " << y << std::endl;
  std::string res;
  std::cin >> res;
  return res == "true";
}

void answer(long long x, long long y) {
  assert(1 <= x && x <= N && 1 <= y && y <= N);
  std::cout << "solution " << x << " " << y << std::endl;
}

std::array<long long, 2> bin_search(std::array<long long, 2> P, int c) {
  bool changed = 1;
  while (changed) {
    long long ans = P[c];
    long long lb = P[c] + 1, rb = N;
    while (lb <= rb) {
      auto m = (lb + rb) / 2;
      auto A = P;
      A[c] = m;
      if (ask(A)) {
        ans = m;
        lb = m + 1;
      } else {
        rb = m - 1; // this is not it
      }
    }
    changed &= ans != P[c];
    P[c] = ans;
  }
  return P;
}

std::array<long long, 2> bin_search_backward(std::array<long long, 2> P, int c) {
  bool changed = 1;
  while (changed) {
    long long ans = P[c];
    long long lb = 1, rb = P[c] - 1;
    while (lb <= rb) {
      auto m = (lb + rb) / 2;
      auto A = P;
      A[c] = m;
      if (ask(A)) {
        ans = m;
        rb = m - 1;
      } else {
        lb = m + 1;
      }
    }
    changed &= ans != P[c];
    P[c] = ans;
  }
  return P;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  std::cin >> N >> P0[0] >> P0[1];

  auto R = bin_search(P0, 0); // find biggest x 
  auto U = bin_search(R, 1); // find biggest y
  auto D = bin_search_backward(R, 1);

  auto len = U[1] - D[1] + 1;
  int offset = len / 2;
  auto P = D;
  P[0] -= offset;
  P[1] += offset;
  answer(P[0], P[1]);
}

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