oj.uz

Submission #966567

# Submission time Handle Problem Language Result Execution time Memory
966567 2024-04-20T04:30:13 Z kilkuwu Aliens (IOI07_aliens) C++17
60 / 100
 2 ms 600 KB 
#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.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

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 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 #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 2 ms 344 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

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