Submission #471900

#	Time	Username	Problem	Language	Result	Execution time	Memory
471900		JovanB	Aliens (IOI07_aliens)	C++17	100 / 100	3 ms	312 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

ll n;

map <pair <ll, ll>, bool> is;

bool ask(ll x, ll y){
    if(x <= 0 || y <= 0 || x > n || y > n) return 0;
    cout << "examine " << x << " " << y << endl;
    string s;
    cin >> s;
    return s == "true";
}

ll sz;

bool check(ll x, ll y){
    for(int i=-2; i<=2; i++){
        for(int j=-2; j<=2; j++){
            if((i+j)%2) continue;
            if(!is[{x + i*sz, y + j*sz}]) return 0;
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    ll x0, y0;
    cin >> n >> x0 >> y0;
    int lm;
    for(lm=0; ; lm++){
        if(!ask(x0 + (1LL << lm), y0)) break;
    }
    ll l = x0 + 1, r = x0 + (1LL << lm) - 1, x2 = x0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(mid, y0)){
            l = mid + 1;
            x2 = mid;
        }
        else r = mid - 1;
    }
    for(lm=0; ; lm++){
        if(!ask(x0 - (1LL << lm), y0)) break;
    }
    l = x0 - (1LL << lm) + 1, r = x0 - 1;
    ll x1 = x0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(mid, y0)){
            r = mid - 1;
            x1 = mid;
        }
        else l = mid + 1;
    }
    sz = x2 - x1 + 1;
    ll xc = (x1+x2)/2;
    for(lm=0; ; lm++){
        if(!ask(x0, y0 + (1LL << lm))) break;
    }
    l = y0 + 1, r = y0 + (1LL << lm) - 1;
    ll y2 = y0;
    while(l <= r){
        ll mid = (l+r)/2;
        if(ask(x0, mid)){
            l = mid + 1;
            y2 = mid;
        }
        else r = mid - 1;
    }
    ll y1 = y2 - sz + 1;
    ll yc = (y1+y2)/2;
    for(int i=-4; i<=4; i++){
        for(int j=-4; j<=4; j++){
            if((i+j)%2) continue;
            ll xn = xc + sz*i;
            ll yn = yc + sz*j;
            is[{xn, yn}] = ask(xn, yn);
        }
    }
    for(int i=-2; i<=2; i++){
        for(int j=-2; j<=2; j++){
            if((i+j)%2) continue;
            if(check(xc + i*sz, yc + j*sz)){
                cout << "solution " << xc + i*sz << " " << yc + j*sz << endl;
                return 0;
            }
        }
    }
    return 0;
}

• 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