#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 |
