Submission #122574

#	Time	Username	Problem	Language	Result	Execution time	Memory
122574		Osama_Alkhodairy	Aliens (IOI07_aliens)	C++17	90 / 100	5 ms	384 KiB

aliens

#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;
    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;
            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);
    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);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10