Submission #114168

#	Time	Username	Problem	Language	Result	Execution time	Memory
114168		zubec	Aliens (IOI07_aliens)	C++14	100 / 100	3 ms	384 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;


bool ask(int x, int y){
    cout << "examine " << x << ' ' << y << endl;
    string s;
    cin >> s;
    return (s == "true");
}

ll crnx, crny, mm;
/*
bool ask(int x, int y){
    if (!(crnx <= x && x <= crnx + mm*5-1 ) || !(crny <= y && y <= crny + mm*5-1))
        return 0;
    ll pr1 = (x-crnx)/mm%2;
    ll pr2 = (y-crny)/mm%2;
    return (pr1^pr2) == 0;
}*/

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    crnx = 5;
    crny = 2;
    mm = 3;

    ll n, x0, y0;

    cin >> n >> x0 >> y0;

    /*for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cout << ask(j, i);
        }
        cout << endl;
    }

    return 0;*/

    ll rgtx0 = 0, lftx0 = 0;

    for (ll i = 1; ; i += i){
        if (x0+i > n || !ask(x0+i, y0)){
            ll l = x0, r = min(n, x0+i);
            while(l < r){
                ll mid = (l+r+1)>>1;
                if (ask(mid, y0))
                    l = mid; else
                    r = mid-1;
            }
            rgtx0 = l;
            break;
        }
    }
    for (ll i = 1; ; i += i){
        if (x0-i <= 0 || !ask(x0-i, y0)){
            ll l = max(1ll, x0-i), r = x0;
            while(l < r){
                ll mid = (l+r)>>1;
                if (ask(mid, y0))
                    r = mid; else
                    l = mid+1;
            }
            lftx0 = l;
            break;
        }
    }
    ll m = rgtx0-lftx0+1;
    ll upy0 = 0;
    for (ll i = 1; ; i += i){
        if (y0-i <= 0 || !ask(lftx0, y0-i)){
            ll l = max(1ll, y0-i), r = y0;
            while(l < r){
                ll mid = (l+r)>>1;
                if (ask(lftx0, mid))
                    r = mid; else
                    l = mid+1;
            }
            upy0 = l;
            break;
        }
    }

    ll up = 0, dwn = 0;
    ll yy = upy0;
    while(yy-2*m >= 1 && ask(lftx0, yy-2*m)){
        ++up;
        yy -= 2*m;
    }
    yy = upy0;
    while(yy+2*m <= n && ask(lftx0, yy+2*m)){
        ++dwn;
        yy += 2*m;
    }

    ll yc = 0;

    if (up == 0 && dwn == 2){
        yc = upy0 + m/2 + m*2;
    } else
    if (up == 1 && dwn == 1){
        yc = upy0 + m/2;
    } else
    if (up == 2 && dwn == 0){
        yc = upy0 + m/2 - m*2;
    } else
    if (up == 0 && dwn == 1){
        yc = upy0 + m/2 + m;
    } else
    if (up == 1 && dwn == 0){
        yc = upy0 + m/2 - m;
    }


    ll lft = 0, rgt = 0;
    ll xx = lftx0;
    while(xx-2*m >= 1 && ask(xx-2*m, upy0)){
        ++lft;
        xx -= 2*m;
    }
    xx = lftx0;
    while(xx+2*m <= n && ask(xx+2*m, upy0)){
        ++rgt;
        xx += 2*m;
    }

    ll xc = 0;

    if (lft == 0 && rgt == 2){
        xc = lftx0 + m/2 + m*2;
    } else
    if (lft == 1 && rgt == 1){
        xc = lftx0 + m/2;
    } else
    if (lft == 2 && rgt == 0){
        xc = lftx0 + m/2 - m*2;
    } else
    if (lft == 0 && rgt == 1){
        xc = lftx0 + m/2 + m;
    } else
    if (lft == 1 && rgt == 0){
        xc = lftx0 + m/2 - m;
    }

    cout << "solution " << xc << ' ' << yc << 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