Submission #647764

#	Time	Username	Problem	Language	Result	Execution time	Memory
647764		alvinpiter	Aliens (IOI07_aliens)	C++17	0 / 100	2 ms	208 KiB

aliens

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

/*
(ex0, ye0) -> Given coordinate with flatten grass
(ex1, ye1) -> The lower-left coordinate of the block where (ex0, ye0) belongs to
(ex2, ye2) -> The lower-left coordinate of the whole structure
*/
int n, m, ex0, ye0, ex1, ye1, ex2, ye2;
int closestUnflattenedInDirection[4];

// up, right, down, left
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

bool isInsideGrid(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= n;
}

bool examine(int x, int y) {
  cout << "examine " << x << " " << y << endl;
  cout << flush;

  string response;
  cin >> response;

  return response == "true";
}

void solution(int x, int y) {
  cout << "solution " << x << " " << y << endl;
  cout << flush;
}

int main() {
  cin >> n >> ex0 >> ye0;

  for (int direction = 0; direction < 4; direction++) {
    int threshold;
    for (int p2 = 1; ; p2 *= 2) {
      int x = ex0 + p2 * dx[direction], y = ye0 + p2 * dy[direction];
      if (!isInsideGrid(x, y) || examine(x, y) == false) {
        threshold = p2;
        break;
      }
    }

    int lo = 1, hi = threshold, mid;
    while (hi >= lo) {
      mid = (lo + hi)/2;

      int x = ex0 + mid * dx[direction], y = ye0 + mid * dy[direction];
      if (isInsideGrid(x, y) && examine(x, y)) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    closestUnflattenedInDirection[direction] = lo;
  }

  m = closestUnflattenedInDirection[0] - closestUnflattenedInDirection[2] - 1;
  ex1 = closestUnflattenedInDirection[3] + 1;
  ye1 = closestUnflattenedInDirection[2] + 1;

  int cntBlocksToTheLeft = 0;
  for (int i = 1; ; i++) {
    if (isInsideGrid(ex1 - i * 2 * m, ye1) && examine(ex1 - i * 2 * m, ye1)) {
      cntBlocksToTheLeft += 1;
    } else {
      break;
    }
  }

  int cntBlocksBelow = 0;
  for (int i = 1; ; i++) {
    if (isInsideGrid(ex1, ye1 - i * 2 * m) && examine(ex1, ye1 - i * 2 * m)) {
      cntBlocksBelow += 1;
    } else {
      break;
    }
  }

  ex2 = ex1 - cntBlocksToTheLeft * 2 * m;
  ye2 = ye1 - cntBlocksBelow * 2 * m;

  solution(ex2 + 2 * m + (m + 1)/2 - 1, ye2 + 2 * m + (m + 1)/2 - 1);
}

• 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