Submission #647773

#TimeUsernameProblemLanguageResultExecution timeMemory
647773alvinpiterAliens (IOI07_aliens)C++14
30 / 100
3 ms336 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...