제출 #1338984

#제출 시각아이디문제언어결과실행 시간메모리
1338984vjudge1Aliens (IOI07_aliens)C++20
0 / 100
1 ms440 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n;
bool query(ll x,ll y) {
    if (x>n || x<0) return false;
    if (y>n || y<0) return false;
    cout << "examine " << x << ' ' << y << endl;
    string answ;
    cin>>answ;
    return answ[0]=='t';
}
void solve() {
    ll x0, y0;
    cin>>n>>x0>>y0;

    ll up = -1;
    ll M = 0;
    for (ll i = 0; i<=32; i++) {
        if (!query(x0+(1LL<<i), y0)) {
            up=x0+(1LL<<i);
            break;
        }
    }
    ll l = x0;
    ll r = up;
    while (r>l) {
        ll mid=r-(r-l)/2;
        if (!query(mid,y0)) l=mid;
        else r=mid-1;
    }
    x0=l-1; // 60, snapped to top
    for (ll i = 0; i<=32; i++) {
        if (!query(x0,y0+(1LL<<i))) {
            up=y0+(1LL<<i);
            break;
        }
    }
    l=y0;
    r=up;
    while (r>l) {
        ll mid=r-(r-l)/2;
        if (!query(mid,y0)) l=mid;
        else r=mid-1;
    }
    y0=l-1; // 124 snapped to top right
    l=0;
    r=n+1;
    while (r>l) {
        ll mid=r-(r-l)/2;
        if (query(x0+mid,y0+mid)) l=mid;
        else r=mid-1;
    }
    x0+=l;
    y0+=l;
    // 158 went to either right or top
    up=-1;
    for (ll i = 0; i<=32; i++) {
        if (query(x0+(1LL<<i), y0)) {
            up=x0+(1LL<<i);
            break;
        }
    }

    if (up!=-1) {
        for (ll i = 0; i<=32; i++) {
            if (!query(x0,y0+(1LL<<i))) {
                up=y0+(1LL<<i);
                break;
            }
        }
        if (up!=-1) {
            l=y0+1;
            r=up;
            while (r>l) {
                ll mid=(l+r)/2;
                if (query(mid,y0)) r=mid;
                else l=mid+1;
            }
            // l is earliest marked pos
            M=abs(l-y0)-1;
        }
    }
    else {
        l=x0+1;
        r=up;
        while (r>l) {
            ll mid=(l+r)/2;
            if (query(mid,y0)) r=mid;
            else l=mid+1;
        }
        // l is earliest marked pos
        M=abs(l-x0)-1;
    }

    if (up!=-1) {
        while (query(x0+2*M,y0)) x0+=2*M;
        while (query(x0,y0+2*M)) y0+=2*M;
    }
    // top left in main diag
    l=0;
    r=n+1;
    while (r>l) {
        ll mid=(l+r)/2;
        if (query(x0-mid,y0-mid)) r=mid;
        else l=mid+1;
    }
    cout << "solution " << x0-l/2 << ' ' << y0-l/2 << endl;
}
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...