oj.uz

Submission #954761

# Submission time Handle Problem Language Result Execution time Memory
954761 2024-03-28T13:57:05 Z vjudge1 Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 712 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, x, y;
map<pair<int, int>, bool> mp;

bool ask(int a, int b) {
  auto it = mp.find(make_pair(a, b));
  if (it != mp.end()) return it->second;

  cout << "examine " << a << " " << b << endl;
  string c; cin >> c;
  return mp[make_pair(a, b)] = (c == "true");
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> x >> y;

  // bs para encontrar el de arriba
  int l = 0;
  int r = n-y;
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x, y + mid) && ask(x, y + mid/2) && ask(x, y + mid/4)) l = mid;
    else r = mid-1;
  }
  int yUp = y+l;
cerr << yUp << endl;
  // bs para encontrar el de abajo
  l = 0;
  r = y-1;
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x, y - mid) && ask(x, y - mid/2) && ask(x, y - mid/4)) l = mid;
    else r = mid-1;
  }
  int yDown = y-l;
cerr << yDown << endl;
  int m = yUp - yDown + 1;
cerr << m << endl;
  // bs para encontrar el de la derecha
  l = 0;
  r = n-x;
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x + mid, y) && ask(x + mid/2, y) && ask(x + mid/4, y)) l = mid;
    else r = mid-1;
  }
  int xRight = x+l;
cerr << xRight << endl;
  // bs para econtrar el de la izquierda
  l = 0;
  r = x-1;
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x - mid, y) && ask(x - mid/2, y) && ask(x - mid/4, y)) l = mid;
    else r = mid-1;
  }
  int xLeft = x-l;
cerr << xLeft << endl;
  // ---

  // bs para encontrar el max de arriba
  l = 0;
  r = (n-yUp) / (m*2);
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x, yUp + m*2 * mid)) l = mid;
    else r = mid-1;
  }
  int yMx = yUp + m*2 * l;
cerr << yMx << endl;
  // bs para encontrar el max de abajo
  l = 0;
  r = (yDown-1) / (m*2);
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(x, yDown - m*2 * mid)) l = mid;
    else r = mid-1;
  }
  int yMn = yDown - m*2 * l;
cerr << yMn << endl;
  // bs para encontrar el max de la derecha
  l = 0;
  r = (n-xRight) / (m*2);
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(xRight + m*2 * mid, y)) l = mid;
    else r = mid-1;
  }
  int xMx = xRight + m*2 * l;
cerr << xMx << endl;
  // bs para econtrar el max de la izquierda
  l = 0;
  r = (xLeft-1) / (m*2);
  while (l < r) {
    int mid = (l+r+1) >> 1;
    if (ask(xLeft - m*2 * mid, y)) l = mid;
    else r = mid-1;
  }
  int xMn = xLeft - m*2 * l;
cerr << xMn << endl;
  // solution
  cout << "solution " << (xMx+xMn)/2 << " " << (yMx+yMn)/2 << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 444 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 1 ms 712 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 448 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 452 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 448 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 448 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 1 ms 708 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 600 KB Output is correct