Submission #647776

#	Time	Username	Problem	Language	Result	Execution time	Memory
647776		alvinpiter	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	292 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define LL long long int

/*
(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 m;
LL n, ex0, ye0, ex1, ye1, ex2, ye2;
int smallestJumpToUnflattenedInDirection[4];

int testingMatrix[100][100];

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

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

bool examine(LL x, LL y) {
  if (!isInsideGrid(x, y)) {
    return false;
  }

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

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

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

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

    smallestJumpToUnflattenedInDirection[direction] = lo;
  }

  m = (ye0 + smallestJumpToUnflattenedInDirection[0]) - (ye0 - smallestJumpToUnflattenedInDirection[2]) - 1;
  ex1 = (ex0 - smallestJumpToUnflattenedInDirection[3]) + 1;
  ye1 = (ye0 - smallestJumpToUnflattenedInDirection[2]) + 1;

  ex2 = ex1;
  ye2 = ye1;

  // Go lower-left while possible
  while (examine(ex2 - m, ye2 - m)) {
    ex2 -= m;
    ye2 -= m;
  }

  // Go left while possible
  while (examine(ex2 - 2 * m, ye2)) {
    ex2 -= 2 * m;
  }

  // Go down while possible
  while (examine(ex2, ye2 - 2 * m)) {
    ye2 -= 2 * m;
  }

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

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

• 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