Submission #954755

#	Time	Username	Problem	Language	Result	Execution time	Memory
954755		vjudge1	Aliens (IOI07_aliens)	C++17	0 / 100	3 ms	452 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, x, y;

bool ask(int a, int b) {
  cout << "examine " << a << " " << b << endl;
  string c; cin >> c;
  return (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;

  // 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;

  int m = yUp - yDown + 1;

  // 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;

  // 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;

  // ---

  // 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, y + m*2 * mid)) l = mid;
    else r = mid-1;
  }
  int yMx = y + m*2 * l;

  // 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, y - m*2 * mid)) l = mid;
    else r = mid-1;
  }
  int yMn = y - m*2 * l;

  // 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(x + m*2 * mid, y)) l = mid;
    else r = mid-1;
  }
  int xMx = x + m*2 * l;

  // 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(x - m*2 * mid, y)) l = mid;
    else r = mid-1;
  }
  int xMn = x - m*2 * l;

  // solution
  cout << "solution " << (xMx+xMn)/2 << " " << (yMx+yMn)/2 << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10