제출 #954761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954761		vjudge1	Aliens (IOI07_aliens)	C++17	100 / 100	2 ms	712 KiB

aliens

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10