oj.uz

Submission #393484

# Submission time Handle Problem Language Result Execution time Memory
393484 2021-04-23T15:07:26 Z armand_gheorghe Aliens (IOI07_aliens) C++14
100 / 100
 2 ms 308 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,p[32];
map<pair<int,int>,int>m;
char s[12];
int query(long long x,long long y)
{
    if(x<1||x>n||y<1||y>n)
        return 0;
    if(m[{x,y}]==0)
    {
        cout<<"examine "<<x<<" "<<y<<'\n';
        cout.flush();
        cin>>s;
        if(s[0]=='t')
            m[{x,y}]=2;
        else
            m[{x,y}]=1;
    }
    return m[{x,y}]-1;
}

int main()
{
    long long 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 308 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 2 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 296 KB Output is correct
3 Correct 1 ms 296 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 2 ms 200 KB Output is correct
3 Correct 2 ms 200 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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