oj.uz

Submission #966580

# Submission time Handle Problem Language Result Execution time Memory
966580 2024-04-20T05:09:13 Z kilkuwu Aliens (IOI07_aliens) C++17
100 / 100
 1 ms 600 KB 
#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.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

Subtask #2
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

Subtask #3
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 #4
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

Subtask #5
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

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

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

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