Submission #45378

#TimeUsernameProblemLanguageResultExecution timeMemory
45378bupjaeUntitled (GCJ18Q_gogopher)C++17
30 / 30
169 ms8304 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...