oj.uz

Submission #412397

# Submission time Handle Problem Language Result Execution time Memory
412397 2021-05-26T19:56:34 Z Dakto Aliens (IOI07_aliens) C++17
70 / 100
 5 ms 296 KB 
#include <bits/stdc++.h>
using namespace std;

bool query(int x, int y){
    cout<<"examine "<<x<<" "<<y<<endl;
    string s;
    cin>>s;
    return s=="true";
}

int main(){
    int n,x,y;
    cin>>n>>x>>y;

    //find right bound
    int l=x, r=n;
    while(l<r){
        int m=(l+r+1)/2;
        if(query(m,y)) l=m;
        else r=m-1;
    }

    if(!query((x+l)/2,y)){
        r=(x+l)/2;
        l=x;
        while(l<r){
            int m=(l+r+1)/2;
            if(query(m,y)) l=m;
            else r=m-1;
        }
    }
    int rb=l;

    l=1, r=x;
    while(l<r){
        int m=(l+r)/2;
        if(query(m,y)) r=m;
        else l=m+1;
    }

    if(!query((x+l)/2,y)){
        l=(x+l)/2;
        r=x;
        while(l<r){
            int m=(l+r)/2;
            if(query(m,y)) r=m;
            else l=m+1;
        }
    }
    int lb=l;

    l=y, r=n;
    while(l<r){
        int m=(l+r+1)/2;
        if(query(x,m)) l=m;
        else r=m-1;
    }

    if(!query(x,(y+l)/2)){
        r=(y+l)/2;
        l=y;
        while(l<r){
            int m=(l+r+1)/2;
            if(query(x,m)) l=m;
            else r=m-1;
        }
    }
    int db=l;

    l=1, r=y;
    while(l<r){
        int m=(l+r)/2;
        if(query(x,m)) r=m;
        else l=m+1;
    }

    if(!query(x,(y+l)/2)){
        l=(y+l)/2;
        r=y;
        while(l<r){
            int m=(l+r)/2;
            if(query(x,m)) r=m;
            else l=m+1;
        }
    }
    int ub=l;

    cerr<<lb<<endl<<rb<<endl<<ub<<endl<<db<<endl;

    int cx=(lb+rb)/2, cy=(ub+db)/2, d=rb-lb+1;

    cerr<<cx<<endl<<cy<<endl<<d<<endl;

    bool up=cy+2*d<=n?query(cx,cy+2*d):0;
    bool down=cy-2*d>0?query(cx,cy-2*d):0;
    bool left=cx-2*d>0?query(cx-2*d,cy):0;
    bool right=cx+2*d<=n?query(cx+2*d,cy):0;

    if(up && down && left && right){
        cout<<"solution "<<cx<<" "<<cy<<endl;
        return 0;
    }
    if(down+up+left+right==3){
        if(!down){
            cout<<"solution "<<cx<<" "<<cy+2*d<<endl;
        }
        if(!up){
            cout<<"solution "<<cx<<" "<<cy-2*d<<endl;
        }
        if(!left){
            cout<<"solution "<<cx+2*d<<" "<<cy<<endl;
        }
        if(!right){
            cout<<"solution "<<cx-2*d<<" "<<cy<<endl;
        }
        return 0;
    }
    if(down && right){
        if(cx + 4*d<=n && query(cx+4*d,cy)){
            cout<<"solution "<<cx+2*d<<" "<<cy-2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx+d<<" "<<cy-d<<endl;
        }
    }

    if(down && left){
        if(cx - 4*d>0 && query(cx-4*d,cy)){
            cout<<"solution "<<cx-2*d<<" "<<cy-2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx-d<<" "<<cy-d<<endl;
        }
    }
    if(up && right){
        if(cx + 4*d<=n && query(cx+4*d,cy)){
            cout<<"solution "<<cx+2*d<<" "<<cy+2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx+d<<" "<<cy+d<<endl;
        }
    }
    if(up && left){
        if(cx - 4*d>0 && query(cx-4*d,cy)){
            cout<<"solution "<<cx-2*d<<" "<<cy+2*d<<endl;
        } 
        else{
            cout<<"solution "<<cx-d<<" "<<cy+d<<endl;
        }
    }
}

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 296 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 292 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 3 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 2 ms 200 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 200 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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