| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 679114 | Hacv16 | Aliens (IOI07_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
int n, x, y, m, numblock, numq;
bool check(int x){ return x > 0 && x <= n ;}
bool query(int x, int y){
if(!check(x) || !check(y)) return false;
assert(++numq <= 300);
cout << "examine " << x << ' ' << y << '\n'; fflush(stdout);
string ans; cin >> ans; return (ans == "true");
}
pair<int, int> findCenter(int x, int y, int m){
int l = 0, r = 2 * n / m, curx = x, cury = y, jump = 0;
//Diagonal jump
while(l <= r){
int mid = (l + r) >> 1;
int nx = curx + m * mid, ny = cury + m * mid;
if(query(nx, ny)) l = mid + 1, jump = mid;
else r = mid - 1;
}
curx += jump * m;
cury += jump * m;
l = 0, r = ((n + m - 1) / m), jump = 0;
//Upwards jump
while(l <= r){
int mid = (l + r) >> 1;
int ny = cury + m * (2 * mid);
if(query(curx, ny)) l = mid + 1, jump = 2 * mid;
else r = mid - 1;
}
cury += jump * m;
//Left jump
l = 0, r = ((n + m - 1)/ m), jump = 0;
while(l <= r){
int mid = (l + r) >> 1;
int nx = curx - m * (2 * mid);
if(query(nx, cury)) l = mid + 1, jump = 2 * mid;
else r = mid - 1;
}
curx -= jump * m;
//move to center of current block
curx += (m - 1) / 2;
cury -= (m - 1) / 2;
//move to center block
l = 0, r = ((n + m - 1) / m), jump = 0;
while(l <= r){
int mid = (l + r) >> 1;
int nx = curx + m * (2 * mid);
if(query(nx, cury)) l = mid + 1, jump = 2 * mid;
else r = mid - 1;
}
numblock = jump + 1;
curx += ((numblock - 1) / 2) * m;
cury -= ((numblock - 1) / 2) * m;
return {curx, cury};
}
pair<int, int> getPos(int x, int y, int dx, int dy){
int pw = 0;
for(int i = 0; i < 31; i++)
if(!query(x + dx * (1 << i), y + dy * (1 << i))){ pw = i; break; }
if(dx == 0 && dy == 1){
int l = y, r = min(n, y + (1 << pw));
while(l <= r){
int mid = (l + r) >> 1;
if(query(x, mid)) l = mid + 1;
else r = mid - 1;
}
return {x, max(y, l - 1)};
}else if(dx == 0 && dy == -1){
int l = max(1, y - (1 << pw)), r = y;
while(l <= r){
int mid = (l + r) >> 1;
if(query(x, mid)) r = mid - 1;
else l = mid + 1;
}
return {x, min(y, r + 1)};
}else{
int l = max(1, x - (1 << pw)), r = x;
while(l <= r){
int mid = (l + r) >> 1;
if(query(mid, y)) r = mid - 1;
else l = mid + 1;
}
return {min(x, r + 1), y};
}
return {x, y};
}
int32_t main(){
cin >> n >> x >> y;
pair<int, int> top = getPos(x, y, 0, 1);
pair<int, int> bot = getPos(x, y, 0, -1);
pair<int, int> lef = getPos(x, y, -1, 0);
int m = top.second - bot.second + 1, cury = top.second, curx = lef.first;
pair<int, int> resp = findCenter(curx, cury, m);
cout << "solution " << resp.first << ' ' << resp.second << '\n';
exit(0);
}