Submission #122583

#TimeUsernameProblemLanguageResultExecution timeMemory
122583Osama_AlkhodairyAliens (IOI07_aliens)C++17
90 / 100
4 ms512 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long ll n, x, y; map <pair <ll, ll>, ll> mp; ll asked = 300; bool ask(ll row, ll col){ if(row < 1 || row > n || col < 1 || col > n) return 0; //~ row--; //~ col--; //~ row %= 6; //~ col %= 6; //~ if(row < 3 && col < 3) return 1; //~ if(row < 3) return 0; //~ if(col < 3) return 0; //~ return 1; if(mp.find({row, col}) != mp.end()) return mp[{row, col}]; asked--; assert(asked >= 0); cout << "examine " << row << " " << col << endl; string ret; cin >> ret; return (mp[{row, col}] = ret == "true"); } void answer(ll row, ll col){ cout << "solution " << row << " " << col << endl; } ll findup(ll row, ll col){ ll l = 1, r = row; while(l <= r){ ll mid = (l + r) / 2; if(ask(mid, col)) r = mid - 1; else l = mid + 1; } return l; } ll findleft(ll row, ll col){ ll l = 1, r = col; while(l <= r){ ll mid = (l + r) / 2; if(ask(row, mid)) r = mid - 1; else l = mid + 1; } return l; } ll finddown(ll row, ll col){ ll l = row, r = n; while(l <= r){ ll mid = (l + r) / 2; if(ask(mid, col)) l = mid + 1; else r = mid - 1; } return r; } ll check(ll m, ll x, ll y){ if(m == 1) return 0; if(m % 2 == 0) return 0; ll ret = 0; for(ll i = -5 ; i <= 5 ; i++){ for(ll j = -5 ; j <= 5 ; j++){ if((i + j) % 2) continue; ll nx = x + i * m; ll ny = y + j * m; if(ask(nx, ny)) ret++; if(ret > 13) return 0; } } return ret == 13; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> x >> y; while(ask(x + 1, y)) x = finddown(x, y); ll h = findup(x, y); ll m = x - h + 1; x = h; if(m % 3 == 0 && check(m / 3, x, y)) m /= 3; else if(m % 5 == 0 && check(m / 5, x, y)) m /= 5; y = findleft(x, y); for(ll i = -5 ; i <= 5 ; i++){ for(ll j = -5 ; j <= 5 ; j++){ if((i + j) % 2) continue; if(ask(x + i * m, y + j * m)){ x += i * m; y += j * m; i = 6; break; } } } answer(x + 2 * m + m / 2, y + 2 * m + m / 2); }
#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...