Submission #122570

#TimeUsernameProblemLanguageResultExecution timeMemory
122570Osama_AlkhodairyAliens (IOI07_aliens)C++17
80 / 100
3097 ms512 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n, x, y; map <pair <int, int>, int> mp; int asked = 300; bool ask(int row, int col){ if(row < 1 || row > n || col < 1 || col > n) return 0; 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(int row, int col){ cout << "solution " << row << " " << col << endl; } int findup(int row, int col){ int l = 1, r = row; while(l <= r){ int mid = (l + r) / 2; if(ask(mid, col)) r = mid - 1; else l = mid + 1; } return l; } int findleft(int row, int col){ int l = 1, r = col; while(l <= r){ int mid = (l + r) / 2; if(ask(row, mid)) r = mid - 1; else l = mid + 1; } return l; } int finddown(int row, int col){ int l = row, r = n; while(l <= r){ int mid = (l + r) / 2; if(ask(mid, col)) l = mid + 1; else r = mid - 1; } return r; } int check(int m, int x, int y){ if(m == 1) return 0; if(m % 2 == 0) return 0; int ret = 0; for(int i = -5 ; i <= 5 ; i++){ for(int j = -5 ; j <= 5 ; j++){ if((i + j) % 2) continue; ret += ask(x + i * m, y + j * m); 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); int h = findup(x, y); int m = x - h + 1; //~ if(m == 5) while(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); //~ assert(m % 2 && m > 1); //~ assert(m == 1); for(int i = -5 ; i <= 5 ; i++){ for(int 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...