Submission #210849

#	Time	Username	Problem	Language	Result	Execution time	Memory
210849		tatyam	Aliens (IOI07_aliens)	C++17	100 / 100	10 ms	420 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(a) for(ll i = 0; i < a; i++)
#define all(a) begin(a), end(a)
#define sum(a) accumulate(all(a), 0LL)

ll n;
bool query(ll x, ll y){
    if(x < 1 || y < 1 || x > n || y > n) return false;
    cout << "examine " << x << ' ' << y << endl;
    string ans;
    cin >> ans;
    return ans[0] == 't';
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> n >> x >> y;
    ll ng = 0, ok = 1;
    while(query(x - ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x - cen, y)) ng = cen;
        else ok = cen;
    }
    x -= ng;
    ng = 0; ok = 1;
    while(query(x, y - ok)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x, y - cen)) ng = cen;
        else ok = cen;
    }
    y -= ng;
    ng = 0; ok = 1;
    while(query(x + ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x + cen, y)) ng = cen;
        else ok = cen;
    }
    ll m = ok;
    x += m / 2;
    y += m / 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x - m, y - m)){
        x -= m;
        y -= m;
    }
    x += m * 2;
    y += m * 2;
    cout << "solution " << x << ' ' << y << endl;
}

• 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: 10 / 10