oj.uz

Submission #881940

# Submission time Handle Problem Language Result Execution time Memory
881940 2023-12-02T10:03:20 Z rxlfd314 Aliens (IOI07_aliens) C++17
80 / 100
 2 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = max(1ll * a, 1ll * (b)))
#define chmin(a, b) (a = min(1ll * a, 1ll * (b)))

int qcnt;

bool ask(int x, int y, bool sw) {
  if (++qcnt > 300)
    exit(0);
  if (sw)
    swap(x, y);
  cout << "examine " << x + 1 << ' ' << y + 1 << endl;
  string s;
  cin >> s;
  return s == "true";
}

ari2 solve(bool sw, int N, int X, int Y) {
  if (sw)
    swap(X, Y);
  int rp = X, hi = N-1;
  #ifdef DEBUG
  cout << "LOL" << endl;
  #endif
  while (rp < hi) {
    int mid = rp + hi + 1 >> 1;
    if (ask(mid, Y, sw))
      rp = mid;
    else
      hi = mid - 1;
  }
  #ifdef DEBUG
  cout << "yeet: " << rp + 1 << endl;
  #endif
  int S;
  if (ask(rp + X >> 1, Y, sw)) {
    int lp = 0;
    hi = X;
    #ifdef DEBUG
    cout << "LOL2" << endl;
    #endif
    while (lp < hi) {
      int mid = lp + hi >> 1;
      if (ask(mid, Y, sw))
        hi = mid;
      else
        lp = mid + 1;
    }
    if (ask(lp + rp >> 1, Y, sw)) {
      if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
        S = rp - lp + 1;
      else
        S = (rp - lp + 1) / 5;
    } else {
      S = (rp - lp + 1) / 3;
    }
  } else {
    int lp = X + rp >> 1;
    hi = rp;
    #ifdef DEBUG
    cout << "LOL3" << endl;
    #endif
    while (lp < hi) {
      int mid = lp + hi >> 1;
      if (ask(mid, Y, sw))
        hi = mid;
      else
        lp = mid + 1;
    }
    S = rp - lp + 1;
  }
  if (rp + 2 * S >= N || !ask(rp + 2 * S, Y, sw))
    rp -= 2 * S;
  if (rp + 4 * S < N && ask(rp + 4 * S, Y, sw))
    return {rp - S + 1, rp + 4 * S};
  if (rp >= 2 * S && ask(rp - 2 * S, Y, sw))
    return {rp - 3 * S + 1, rp + 2 * S};
  return {rp - 2 * S + 1, rp + 3 * S};
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, X, Y;
  cin >> N >> X >> Y, X--, Y--;
  auto [a, b] = solve(false, N, X, Y);
  auto [c, d] = solve(true, N, X, Y);
  cout << "solution " << (a + b) / 2 + 1 << ' ' << (c + d) / 2 + 1 << endl;
}

Compilation message

aliens.cpp: In function 'ari2 solve(bool, int, int, int)':
aliens.cpp:37:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = rp + hi + 1 >> 1;
      |               ~~~~~~~~^~~
aliens.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   if (ask(rp + X >> 1, Y, sw)) {
      |           ~~~^~~
aliens.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |       int mid = lp + hi >> 1;
      |                 ~~~^~~~
aliens.cpp:60:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     if (ask(lp + rp >> 1, Y, sw)) {
      |             ~~~^~~~
aliens.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |       if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
      |                ~~~^~~~
aliens.cpp:61:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |       if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
      |               ~~~~~~~~~~~~~~~^~~~
aliens.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |     int lp = X + rp >> 1;
      |              ~~^~~~
aliens.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |       int mid = lp + hi >> 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 344 KB Output is correct

Subtask #2
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 #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 0 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 0 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 0 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
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 2 ms 344 KB too many queries
3 Halted 0 ms 0 KB -