Submission #543804

#TimeUsernameProblemLanguageResultExecution timeMemory
543804timreizinAliens (IOI07_aliens)C++17
0 / 100
2 ms464 KiB
#include <iostream> #include <vector> #include <array> #include <numeric> #include <cassert> #include <tuple> using namespace std; using ll = long long; int N; int table[100][100]; bool ask(int x, int y) { if (x < 1 || y < 1 || y > N || x > N) return false; cout << "examine " << x << ' ' << y << '\n'; cout.flush(); string res; cin >> res; return res == "true"; } tuple<int, int, int> find(int xl, int xr, int y0) { for (int i = 0; i < 3; ++i) { for (int j = i; j < 3; ++j) { if ((xr - xl + 1) % ((j - i) * 2 + 1) != 0) continue; int m = (xr - xl + 1) / ((j - i) * 2 + 1); int e = xl - (2 * i * m); bool flag = true; for (int k = 0; k < 3; ++k) { flag &= ask(e + k * 2 * m, y0); flag &= !ask(e + k * 2 * m - 1, y0); flag &= !ask(e + (k * 2 + 1) * m, y0); flag &= ask(e + (k * 2 + 1) * m - 1, y0); } if (flag) return {e, m, 0}; } } for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { if ((xr - xl + 1) % ((j - i) * 2 + 1) != 0) continue; int m = (xr - xl + 1) / ((j - i) * 2 + 1); int e = xl - (2 * i * m); bool flag = true; for (int k = 0; k < 2; ++k) { flag &= ask(e + k * 2 * m, y0); flag &= !ask(e + k * 2 * m - 1, y0); flag &= !ask(e + (k * 2 + 1) * m, y0); flag &= ask(e + (k * 2 + 1) * m - 1, y0); } if (flag) return {e, m, 1}; } } assert(false); return {-1, -1, -1}; } void fillsqr(int x, int y, int m) { for (int i = x; i < x + m; ++i) { for (int j = y; j < y + m; ++j) { table[i][j] = 1; } } } int main() { /*fillsqr(5, 2, 3); fillsqr(11, 2, 3); fillsqr(17, 2, 3); fillsqr(5, 8, 3); fillsqr(11, 8, 3); fillsqr(17, 8, 3); fillsqr(5, 14, 3); fillsqr(11, 14, 3); fillsqr(17, 14, 3); fillsqr(8, 5, 3); fillsqr(14, 5, 3); fillsqr(8, 11, 3); fillsqr(14, 11, 3);*/ cin.tie(0)->sync_with_stdio(0); int n, x0, y0; cin >> n >> x0 >> y0; N = n; int l = 1, r = x0; while (l < r) { int m = (l + r) >> 1; if (ask(m, y0)) r = m; else l = m + 1; } int xl = l; l = x0; r = n; while (l < r) { int m = (l + r) >> 1; if (ask(m, y0)) l = m + 1; else r = m; } int xr = l - 1; auto [x, m, t] = find(xl, xr, y0); if (t) { x -= m; y0 -= m; } l = y0; r = y0 + m; while (l < r) { int m = (l + r) >> 1; if (ask(x, m)) l = m + 1; else r = m; } int y = l - 1; y -= m - 1; while (ask(x, y - m)) y -= m; x += 2 * m + m / 2; y += 2 * m + m / 2; cout << "solution " << x << ' ' << y << '\n'; return 0; } /* false true *3 false *3 */
#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...