oj.uz

Submission #551608

# Submission time Handle Problem Language Result Execution time Memory
551608 2022-04-21T07:09:42 Z krit3379 Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 208 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 5005
#define ll long long

int a[5][5];
ll n;

bool query(int x,int y){
    if(x<1||y<1||x>n||y>n)return false;
    string s;
    cout<<"examine "<<x<<" "<<y<<endl;
    cin>>s;
    return s[0]=='t';
}

void sol(int x,int y){
    cout<<"solution "<<x<<" "<<y<<endl;
}

void jump(ll x,ll y,ll di,ll dj,ll &xx,ll &yy){
    ll lx,ly,i,l,r,mid;
    lx=x,ly=y;
    for(i=0;0<x&&x<=n&&0<y&&y<=n;i++){
        x+=(1<<i)*di;
        x=min(x,n+1);
        x=max(x,0ll);
        y+=(1<<i)*dj;
        y=min(y,n+1);
        y=max(y,0ll);
        if(!query(x,y))break;
        lx=x;
        ly=y;
    }
    if(y==ly){
        if(lx<x){
            l=lx+1,r=x-1;
            while(l<=r){
                mid=(l+r)/2;
                if(query(mid,y))lx=mid,l=mid+1;
                else r=mid-1;
            }
        }
        else{
            l=x+1,r=lx-1;
            while(l<=r){
                mid=(l+r)/2;
                if(query(mid,y))lx=mid,r=mid-1;
                else l=mid+1;
            }
        }
    }
    else{
        l=y+1,r=ly-1;
        while(l<=r){
            mid=(l+r)/2;
            if(query(x,mid))ly=mid,r=mid-1;
            else l=mid+1;
        }
    }
    xx=lx,yy=ly;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    ll i,j,m,x,y,xr,yr,xl,yl,xd,yd,xc,yc,cnt=0;
    cin>>n>>x>>y;
    jump(x,y,1,0,xr,yr);
    jump(x,y,-1,0,xl,yl);
    jump(x,y,0,-1,xd,yd);
    m=xr-xl+1;
    xc=(xl+xr)/2;
    yc=yd+m/2;
    for(i=-2;i<=2;i++)for(j=-2;j<=2;j++)a[i+2][j+2]=query(xc+j*m,yc+i*m),cnt+=a[i+2][j+2];
    if(cnt==13)sol(xc,yc);
    else if(cnt==8){
        if(a[0][2]+a[4][2]+a[2][0]+a[2][4]==2){
            if(a[0][0])sol(xc-m,yc-m);
            else if(a[0][4])sol(xc+m,yc-m);
            else if(a[4][0])sol(xc-m,yc+m);
            else if(a[4][4])sol(xc+m,yc+m);
        }
        else{
            if(!a[0][2])sol(xc,yc+2*m);
            else if(!a[4][2])sol(xc,yc-2*m);
            else if(!a[2][0])sol(xc+2*m,yc);
            else if(!a[2][4])sol(xc-2*m,yc);
        }
    }
    else if(cnt==5){
        if(a[0][0])sol(xc-2*m,yc-2*m);
        else if(a[0][4])sol(xc+2*m,yc-2*m);
        else if(a[4][0])sol(xc-2*m,yc+2*m);
        else if(a[4][4])sol(xc+2*m,yc+2*m);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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