oj.uz

Submission #393480

# Submission time Handle Problem Language Result Execution time Memory
393480 2021-04-23T14:56:57 Z armand_gheorghe Aliens (IOI07_aliens) C++14
80 / 100
 5 ms 256 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 200 KB Output is correct
2 Runtime error 4 ms 200 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Runtime error 5 ms 200 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -