oj.uz

Submission #647774

# Submission time Handle Problem Language Result Execution time Memory
647774 2022-10-04T04:56:43 Z alvinpiter Aliens (IOI07_aliens) C++14
30 / 100
 3 ms 208 KB 
#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;

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

  int cntBlocksBelow = 0;
  for (int i = 1; ; i++) {
    if (examine(ex1, ye1 - (LL) 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Incorrect 3 ms 208 KB Incorrect
4 Halted 0 ms 0 KB -