Submission #521655

#	Time	Username	Problem	Language	Result	Execution time	Memory
521655		perchuts	Aliens (IOI07_aliens)	C++17	0 / 100	1 ms	204 KiB

aliens

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

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

int main(){_
    ll n,x0,y0;cin>>n>>x0>>y0;
    //find rightmost, leftmost and topmost coordinates using binsearch
    query(x0,y0);
    ll l,r,leftmost = x0,rightmost = x0,topmost = y0;
    //leftmost
    while(true){
        bool ok = false;
        l = 1, r = leftmost-1LL;
        while(l<=r){
        ll md = l + (r-l+1LL)/2;
        if(query(md,y0)){
            leftmost = md;
            r = md-1LL;
            ok = true;
        }else{
            l = md+1LL;
        }   
    }
        if(!ok)break;
    }
    //rightmost
    while(true){
        bool ok = false;
        l = rightmost + 1LL, r = n;
        while(l<=r){
            ll md = l + (r-l+1LL)/2;
            if(query(md,y0)){
                rightmost = md;
                l = md+1LL;
                ok = true;
            }else{
                r = md-1LL;
            }
        }
        if(!ok)break;        
    }
    //topmost
    l = 1LL, r = y0;
    while(true){
        l = topmost+1, r = n;
        bool ok = false;
        while(l<=r){
        ll md = l + (r-l+1)/2;
        if(query(x0,md)){
            topmost = md;
            l = md+1;
            ok = true;
        }else{
            r = md-1;
        }
        }
        if(!ok)break;
    }

    ll len = rightmost - leftmost + 1;
    ll xc = leftmost + len/2, yc = topmost - len/2;
    cout<<"solution "<<xc<<" "<<yc<<endl;
}

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