| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 157359 | my99n | Aliens (IOI07_aliens) | C++14 | 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>
// #include"alienslib.h"
// #include "alienslib.cpp"
int examine(int x, int y) {
string res;
cout << "examine " << x << ' ' << y << endl;
cin >> res;
return res == "true";
}
void solution (int x, int y) {
cout << "solution " << x << ' ' << y << endl;
}
void get_size_and_start(int &N, int &X0, int &Y0){
scanf("%d %d %d", &N, &X0, &Y0);
}
using namespace std;
int n;
int bsearch (bool axis, bool high, int l, int r, int st){
if (l == r) return l;
if (high) {
if (axis) {
int mid = (l+r+1)/2;
int res = examine(mid, st);
assert(res != -1);
if (res) return bsearch(axis, high, mid, r, st);
else return bsearch(axis, high, l, mid-1, st);
}
else {
int mid = (l+r+1)/2;
int res = examine(st, mid);
assert(res != -1);
if (res) return bsearch(axis, high, mid, r, st);
else return bsearch(axis, high, l, mid-1, st);
}
}
else {
if (axis) {
int mid = (l+r)/2;
int res = examine(mid, st);
assert(res != -1);
if (res) return bsearch(axis, high, l, mid, st);
else return bsearch(axis, high, mid+1, r, st);
}
else {
int mid = (l+r)/2;
int res = examine(st, mid);
assert(res != -1);
if (res) return bsearch(axis, high, l, mid, st);
else return bsearch(axis, high, mid+1, r, st);
}
}
return -1;
}
int bound (bool axis, bool high, int x, int y, int a = 1) {
// if axis == 1, y must be static and vice versa
if (x > n) return n;
if (x <= 0) return 0;
if (high) {
// operator +
if (axis) {
int res = examine(x+a, y);
assert(res != -1);
if (res) return bound(axis, high, x+a, y, a<<1);
else return bsearch(axis, high, x, x+a, y);
}
else {
int res = examine(x, y+a);
assert(res != -1);
if (res) return bound(axis, high, x, y+a, a<<1);
else return bsearch(axis, high, y, y+a, x);
}
}
else {
// operator -
if (axis) {
int res = examine(x-a, y);
assert(res != -1);
if (res) return bound(axis, high, x-a, y, a<<1);
else return bsearch(axis, high, x-a, x, y);
}
else {
int res = examine(x, y-a);
assert(res != -1);
if (res) return bound(axis, high, x, y-a, a<<1);
else return bsearch(axis, high, y-a, y, x);
}
}
return -1;
}
int main(){
int x, y;
get_size_and_start(n, x, y);
int xh = bound(1, 1, x, y);
int yh = bound(0, 1, x, y);
int xl = bound(1, 0, x, y);
int yl = bound(0, 0, x, y);
int xc = (xh+xl+1)/2;
int yc = (yh+yl+1)/2;
// cerr << xc << ' ' << yc << endl;
int size = xh-xl+1;
assert(size == yh-yl+1);
vector<pair<int,int>> around, twostep;
for(int i = -1; i <= 1; i+=2){
for(int j = -1; j <= 1; j+=2){
if (examine(xc+i*size, yc+j*size) == 1) around.push_back({i, j});
if (examine(xc+i*size*2, yc+j*size*2)) twostep.push_back({i, j});
}
}
if (around.size() == 1) {
solution(xc+around[0].first*size*2, yc+around[0].second*size*2);
return 0;
}
if (around.size() == 2) {
if (around[0].first == around[1].first) {
solution(xc+around[0].first*2*size, yc);
return 0;
}
if (around[0].second == around[1].second) {
solution(xc,around[0].second*2*size+yc);
return 0;
}
}
if (twostep.size() == 1) {
solution(xc+twostep[0].first*size, yc+twostep[0].second*size);
return 0;
}
else {
solution(xc, yc);
return 0;
}
assert(false);
return 0;
}