Submission #781175

#TimeUsernameProblemLanguageResultExecution timeMemory
781175raysh07Aliens (IOI07_aliens)C++17
0 / 100
3 ms464 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 #define f first #define s second mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); int n, x, y, m; int q = 0; bool query(int x1, int y1){ if (x1 < 1 || x1 > n || y1 < 1 || y1 > n) return false; cout << "examine " << x1 << " " << y1 << endl; q++; assert(q <= 300); string ok; cin >> ok; if (ok == "true") return true; return false; } bool check(int x1, int y1){ if (!query(x1, y1)) return false; x1 = (x1 + x) / 2; y1 = (y1 + y) / 2; if (!query(x1, y1)) return false; x1 = (x1 + x) / 2; y1 = (y1 + y) / 2; if (!query(x1, y1)) return false; return true; } bool areyouok(int dx, int dy){ int x1 = x + dx * m; int y1 = y + dy * m; return query(x1, y1); } void print(int l, int r, int u, int d){ cout << "solution " << (l + r) / 2 << " " << (u + d) / 2 << endl; } void Solve() { cin >> n; cin >> x >> y; int ll = 1, rl = x; while (ll != rl){ int mid = (ll + rl) / 2; if (check(mid, y)) rl = mid; else ll = mid + 1; } int l = ll; // cout << "FOUND OUT LEFT " << l << endl; ll = x, rl = n; while (ll != rl){ int mid = (ll + rl + 1) / 2; if (check(mid, y)) ll = mid; else rl = mid - 1; } int r = ll; // cout << "FOUND OUT RIGHT " << r << endl; ll = 1, rl = y; while (ll != rl){ int mid = (ll + rl) / 2; if (check(x, mid)) rl = mid; else ll = mid + 1; } int u = ll; // cout << "FOUND OUT UP " << u << endl; ll = y, rl = n; while (ll != rl){ int mid = (ll + rl + 1) / 2; if (check(x, mid)) ll = mid; else rl = mid - 1; } int d = ll; // cout << "FOUND OUT DOWN " << d << endl; m = (d - u + 1); assert(m == (r - l + 1)); for (int i = 0; i < 5; i++){ for (int j = 0; j < 5; j++){ if ((i + j) % 2 == 1) continue; bool good = true; for (int i1 = 0; i1 < 5; i1++){ for (int j1 = 0; j1 < 5; j1++){ if ((i1 + j1) % 2 == 0){ good &= areyouok(i1 - i, j1 - j); } } } if (good){ l += m * (3 - i); r += m * (3 - i); u += m * (3 - i); d += m * (3 - i); print(l, r, u, d); return; } } } } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // freopen("in", "r", stdin); // freopen("out", "w", stdout); // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }
#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...