Submission #499964

#	Time	Username	Problem	Language	Result	Execution time	Memory
499964		gg123_pe	Aliens (IOI07_aliens)	C++17	0 / 100	3 ms	284 KiB

aliens

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

typedef long long ll; 
typedef pair <pair<char,char>, pair<char,char>> T; 
#define f(i,a,b) for(ll i = a; i < b; i++)


ll n, x, y, l; 

bool ask(ll a, ll b){
    cout << "examine " << a << " " << b << endl; 
    string s; cin >> s; 
    fflush(stdout);
    return (s == "true" ? 1 : 0);
}
int main(){
    cin >> n >> x >> y; 
    ll up, down, left, right; 

    // up 
    ll ini = y, fin = n; 
    f(i,0,32){
        ll l = x, r = y+(1LL<<i); 
        if(r <= n){
           if(!ask(l,r)) {
               fin = r; 
               break; 
           }
           ini = r; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin+1)>>1; 
        if(ask(x,ini)) ini = m;
        else fin = m-1; 
    }
    up = ini; 
    // right 
    ini = x, fin = n; 
    f(i,0,32){
        ll l = x + (1LL<<i), r = y; 
        if(l <= n){
           if(!ask(l,r)) {
               fin = l; 
               break; 
            }
            ini = l; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin+1)>>1; 
        if(ask(x,ini)) ini = m;
        else fin = m-1; 
    }
    right = ini;
    // left 
    ini = 1, fin = x; 
    f(i,0,32){
        ll l = x - (1LL<<i), r = y; 
        if(l >= 1){
           if(!ask(l,r)) {
               ini = l; 
               break; 
            }
            fin = l; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin)>>1; 
        if(ask(x,ini)) fin = m;
        else ini = m+1; 
    }
    left = ini;
    // down 
    ini = 1, fin = y; 
    f(i,0,32){
        ll l = x, r = y - (1LL<<i); 
        if(r >= 1){
           if(!ask(l,r)) {
               ini = r; 
               break; 
            }
            fin = r; 
        }
    }
    while(ini < fin){
        ll m = (ini+fin)>>1; 
        if(ask(x,ini)) fin = m;
        else ini = m+1; 
    }
    down = ini;

    x = (left+right)/2, y = (up+down)/2, l = (up-down+1); 

    vector <pair<ll,ll>> centers; 
    for(ll i = x-4*l; i <= x+4*l; i += 2*l){
        for(ll j = y-4*l; j <= y+4*l; j += 2*l){
            if(i >= 1 and i <= n and j <= n and j >= 1){
                if(ask(i,j)) centers.push_back({i,j});
            }
        }
    }
    cout << "solution " << centers[4].first << " " << centers[4].second << endl; 
    fflush(stdout); 
    return 0; 
}

• 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