Submission #647773

#	Time	Username	Problem	Language	Result	Execution time	Memory
647773		alvinpiter	Aliens (IOI07_aliens)	C++14	30 / 100	3 ms	336 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(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;
}

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 (!isInsideGrid(x, y) || 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 (isInsideGrid(x, y) && 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;

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

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

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