Submission #966580

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

aliens

#include <bits/stdc++.h>

#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

#define int int64_t

int N;
std::array<int, 2> P0;
int ask(std::array<int, 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(int x, int y) {
  assert(1 <= x && x <= N && 1 <= y && y <= N);
  std::cout << "solution " << x << " " << y << std::endl;
}

std::array<int, 2> bin_search(std::array<int, 2> P, int c) {
  int ans = P[c];
  int 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
    }
  }
  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
  int rb = std::min(N - U[0], N - U[1]);
  int lb = 1;
  int ans = 0;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    if (ask({U[0] + m, U[1] + m})) {
      ans = m;
      lb = m + 1;
    } else {
      rb = m - 1;
    }
  } 
  auto UR = U;
  UR[0] += ans;
  UR[1] += ans;
  lb = 1;
  rb = std::min(U[0] - 1, U[1] - 1);  
  ans = 0;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    if (ask({U[0] - m, U[1] - m})) {
      ans = m;
      lb = m + 1;
    } else {
      rb = m - 1;
    }
  }

  auto LL = U;
  LL[0] -= ans;
  LL[1] -= ans;
  U = {(LL[0] + UR[0]) / 2, (LL[1] + UR[1]) / 2};
  rb = std::min(U[0] - 1, N - U[1]); // -, +
  lb = 1;
  ans = 0;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    if (ask({U[0] - m, U[1] + m})) {
      ans = m;
      lb = m + 1;
    } else {
      rb = m - 1;
    }
  } 
  UR = U;
  UR[0] -= ans;
  UR[1] += ans;
  lb = 1;
  rb = std::min(N - U[0], U[1] - 1);  
  ans = 0;
  while (lb <= rb) {
    int m = (lb + rb) / 2;
    if (ask({U[0] + m, U[1] - m})) {
      ans = m;
      lb = m + 1;
    } else {
      rb = m - 1;
    }
  }
  LL = U;
  LL[0] += ans;
  LL[1] -= ans;
  U = {(LL[0] + UR[0]) / 2, (LL[1] + UR[1]) / 2};
  answer(U[0], U[1]); 
}
/*
45 9
19 9
23 23

1 9 0
10 18 1
19 27 2
28 36 3
37 45 4
3 0
1999999995 399999999
177777777 299999999
999999998 999999998

*/

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