oj.uz

Submission #882005

# Submission time Handle Problem Language Result Execution time Memory
882005 2023-12-02T11:53:09 Z rxlfd314 Aliens (IOI07_aliens) C++17
100 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // rip N <= 2 * 1e9
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 N;

bool ask(int x, int y, bool sw, bool bs = false) {
  if ((x < 0 || y < 0) && bs)
    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 X, int Y) {
  if (sw)
    swap(X, Y);
  int rp = X, hi = N-1;
  while (rp < hi) {
    int mid = rp + hi + 1 >> 1;
    if (ask(mid, Y, sw, true))
      rp = mid;
    else
      hi = mid - 1;
  }
  int S;
  if (ask(rp + X >> 1, Y, sw)) {
    int lp = 0;
    hi = X;
    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;
    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 X, Y;
  cin >> N >> X >> Y, X--, Y--;
  auto [a, b] = solve(false, X, Y);
  auto [c, d] = solve(true, X, Y);
  cout << "solution " << (a + b) / 2 + 1 << ' ' << (c + d) / 2 + 1 << endl;
}

Compilation message

aliens.cpp: In function 'ari2 solve(bool, ll, ll)':
aliens.cpp:36:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = rp + hi + 1 >> 1;
      |               ~~~~~~~~^~~
aliens.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   if (ask(rp + X >> 1, Y, sw)) {
      |           ~~~^~~
aliens.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = lp + hi >> 1;
      |                 ~~~^~~~
aliens.cpp:53:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     if (ask(lp + rp >> 1, Y, sw)) {
      |             ~~~^~~~
aliens.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |       if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
      |                ~~~^~~~
aliens.cpp:54:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |       if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
      |               ~~~~~~~~~~~~~~~^~~~
aliens.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int lp = X + rp >> 1;
      |              ~~^~~~
aliens.cpp:65:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |       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 0 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 0 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 0 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 340 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