Submission #157319

#	Time	Username	Problem	Language	Result	Execution time	Memory
157319		Autoratch	Aliens (IOI07_aliens)	C++14	0 / 100	3 ms	380 KiB

aliens

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

int n,x,y,ox,oy,l,r,up,lo,sz;

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

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

    cin >> n >> x >> y;
    ox = x,oy = y;
    
    l = x,r = n;
    for(int i = 1;x+i <= n;i*=2)
    {
        if(!check(x+i,y)){ r = x+i; break; }
        else if(!check(x+i-1,y)){ r = x+i-1; break; }
        else l = x+i;
        x+=i;
    }
    while(l<r)
    {
        int m = (l+r)/2;
        if(check(m,y))
        { 
            if(!check(m+1,y)){ l = m; break; } 
            else l = m+1; 
        }
        else r = m-1;
    }
    up = l;
    x = ox,y = oy;
    l = 1,r = x;
    for(int i = 1;x-i >= 1;i*=2)
    {
        if(!check(x-i,y)){ l = x-i; break; }
        else if(!check(x+i-1,y)){ l = x-i+1; break; }
        else r = x-i;
        x-=i;
    }
    while(l<r)
    {
        int m = (l+r)/2;
        if(check(m,y))
        {
            if(!check(m-1,y)){ l = m; break; }
            else r = m-1;
        }
        else l = m+1;
    }
    lo = l,sz = lo-up+1;
    x = ox,y = oy;
    while(check(x-sz*2,y-sz*2)) x-=sz*2,y-=sz*2;
    while(check(x-sz*2,y)) x-=sz*2;
    while(check(x,y-sz*2)) y-=sz*2;
    l = x-sz,r = x;
    while(l<r)
    {
        int m = (l+r)/2;
        if(check(m,y))
        {
            if(!check(m-1,y)){ l = m; break; }
            else r = m-1;
        }
        else l = m+1;
    }
    x = l;
    l = y-sz,r = y;
    while(l<r)
    {
        int m = (l+r)/2;
        if(check(x,m))
        {
            if(!check(x,m-1)){ l = m; break; }
            else r = m-1;
        }
        else l = m+1;
    }
    y = l;
    cout << x+sz*2+sz/2 << ' ' << y+sz*2+sz/2;
}

• 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