답안 #45378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45378 2018-04-13T05:33:54 Z bupjae Go, Gopher! (GCJ18Q_gogopher) C++17
30 / 30
169 ms 8304 KB
#include <algorithm>
#include <array>
#include <iostream>
#include <memory>

using namespace std;

bool main2() {
  int a;
  cin >> a;
  auto orchardPtr = make_unique<array<array<int, 1002>, 1002>>();
  auto commandPtr = make_unique<array<array<int, 1002>, 1002>>();
  auto& orchard = *orchardPtr;
  auto& command = *commandPtr;

  cout << "500 500" << endl;
  int minX = 1001, minY = 1001, maxX = 0, maxY = 0;
  while (true) {
    int x, y;
    cin >> x >> y;
    if (x == 0 && y == 0) return true;
    if (x == -1 && y == -1) return false;
    minX = min(minX, x);
    minY = min(minY, y);
    maxX = max(maxX, x);
    maxY = max(maxY, y);
    if (orchard[x][y] == 0) {
      orchard[x][y] = 1;
      for (int i = x - 1; i <= x + 1; i++) {
        for (int j = y - 1; j <= y + 1; j++) {
          command[i][j]++;
        }
      }
    }

    int q = 1000;
    if ((maxX - minX + 3) * (maxY - minY + 3) < a) {
      q = min({command[minX - 1][minY - 1], command[minX - 1][maxY + 1],
               command[maxX + 1][minY - 1], command[maxX + 1][maxY + 1]});
      if (q == command[minX - 1][minY - 1]) {
        x = minX - 1;
        y = minY - 1;
      } else if (q == command[minX - 1][maxY + 1]) {
        x = minX - 1;
        y = maxY + 1;
      } else if (q == command[maxX + 1][minY - 1]) {
        x = maxX + 1;
        y = minY - 1;
      } else {
        x = maxX + 1;
        y = maxY + 1;
      }
    } else if (maxX - minX < 2 && maxY - minY < 2) {
      x = minX;
      y = minY;
    } else if ((maxX - minX + 1) * (maxY - minY + 1) >= a) {
      if (maxX - minX < 2) {
        x = minX;
        for (int i = minY + 1; i < maxY; i++) {
          if (q > command[minX][i]) {
            q = command[minX][i];
            y = i;
          }
        }
      } else if (maxY - minY < 2) {
        y = minY;
        for (int i = minX + 1; i < maxX; i++) {
          if (q > command[i][minY]) {
            q = command[i][minY];
            x = i;
          }
        }
      } else {
        for (int i = minX + 1; i < maxX; i++) {
          for (int j = minY + 1; j < maxY; j++) {
            if (q > command[i][j]) {
              q = command[i][j];
              x = i;
              y = j;
            }
          }
        }
      }
    } else {
      bool extensionX;
      if (maxX - minX < 2) {
        extensionX = true;
      } else if (maxY - minY < 2) {
        extensionX = false;
      } else {
        int delta = a - (maxX - minX + 1) * (maxY - minY + 1);
        int deltaExtX = maxY - minY + 1;
        int deltaExtY = maxX - minX + 1;
        if (delta <= deltaExtX && delta <= deltaExtY) {
          extensionX = min(deltaExtX, deltaExtY) == deltaExtX;
        } else if (delta <= deltaExtX) {
          extensionX = true;
        } else if (delta <= deltaExtY) {
          extensionX = false;
        } else {
          extensionX = max(deltaExtX, deltaExtY) == deltaExtX;
        }
      }
      if (extensionX) {
        for (int i = minY + 1; i < maxY; i++) {
          if (q > command[minX][i]) {
            q = command[minX][i];
            x = minX;
            y = i;
          }
          if (q > command[maxX][i]) {
            q = command[maxX][i];
            x = maxX;
            y = i;
          }
        }
      } else {
        for (int i = minX + 1; i < maxX; i++) {
          if (q > command[i][minY]) {
            q = command[i][minY];
            x = i;
            y = minY;
          }
          if (q > command[i][maxY]) {
            q = command[i][maxY];
            x = i;
            y = maxY;
          }
        }
      }
    }
    cout << x << " " << y << endl;
  }
}

int main() {
  ios::sync_with_stdio(false);

  int t;
  cin >> t;
  for (; t > 0; t--) {
    if (!main2()) break;
  }
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 8184 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 8304 KB Output is correct