Submission #393480

#	Time	Username	Problem	Language	Result	Execution time	Memory
393480		armand_gheorghe	Aliens (IOI07_aliens)	C++14	80 / 100	5 ms	256 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
int n,p[32];
char s[12];
bool query(int x,int y)
{
    if(x<1||x>n||y<1||y>n)
        return 0;
    cout<<"examine "<<x<<" "<<y<<'\n';
    cout.flush();
    cin>>s;
    if(s[0]=='t')
        return 1;
    else
        return 0;
}

int main()
{
    int x,y,i,m,last,st,dr,mij,left,right,down,up,xx,yy;
    cin>>n>>x>>y;
    p[0]=1;
    for(i=1;i<=30;i++)
        p[i]=p[i-1]*2;
    //stanga
    last=y;
    for(i=0;i<=30;i++)
    {
        if(query(x,y-p[i])==0)
            break;
        last=y-p[i];
    }
    st=y-p[i];
    dr=last;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(query(x,mij)==0)
            st=mij+1;
        else
            dr=mij-1;
    }
    left=st;
    //dreapta
    last=y;
    for(i=0;i<=30;i++)
    {
        if(query(x,y+p[i])==0)
            break;
        last=y+p[i];
    }
    st=last;
    dr=y+p[i];
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(query(x,mij)==0)
            dr=mij-1;
        else
            st=mij+1;
    }
    right=dr;
    //jos
    last=x;
    for(i=0;i<=30;i++)
    {
        if(query(x+p[i],y)==0)
            break;
        last=x+p[i];
    }
    st=last;
    dr=x+p[i];
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(query(mij,y)==0)
            dr=mij-1;
        else
            st=mij+1;
    }
    down=dr;
    //sus
    m=right-left+1;
    up=down-m+1;
    //centrez in patratul acesta
    x=up+m/2;
    y=left+m/2;
    //centrez pe diagonala secundara
    st=0;
    xx=x;
    yy=y;
    while(query(xx+m,yy-m)==1)
    {
        st++;
        xx+=m;
        yy-=m;
    }
    dr=0;
    while(query(x-m,y+m)==1)
    {
        st++;
        x-=m;
        y+=m;
    }
    x+=(st+dr)/2*m;
    y-=(st+dr)/2*m;
    //centrez pe diagonala principala
    while(query(x-m,y-m)==1)
    {
        x-=m;
        y-=m;
    }
    x+=2*m;
    y+=2*m;
    cout<<"solution "<<x<<" "<<y<<'\n';
    cout.flush();
    return 0;
}

• 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: 0 / 10
• Subtask 10: 0 / 10