oj.uz

Submission #362892

# Submission time Handle Problem Language Result Execution time Memory
362892 2021-02-04T16:06:04 Z cig32 Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 364 KB 
#include"bits/stdc++.h"
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
int examine(int X,int Y){
    cout<<"examine "<<X<<" "<<Y<<"\n";
    fflush(stdout);
    string x;
    cin >>x;
    if(x=="false")return 0;
    return 1;
}
void solution(int XC,int YC){
    cout<<"solution "<<XC<<" "<<YC<<"\n";
    fflush(stdout);
}
void findCenter(int N,int X0,int Y0){
    int left_bound, right_bound, up_bound, down_bound;
    //right bound
    int teehee=N;
    int randompoint;
    while(X0<teehee){
        if(examine(teehee,Y0)){
            break;
        }
        randompoint=teehee;
        teehee=(X0+teehee)/2;
    }
    //Check same subsquare
    bool is_same_subsquare=1;
    int temp_lb,temp_rb=teehee;
    for(int i=0;i<2;i++){
        int mid=(X0+temp_rb)/2;
        if(examine(mid,Y0)==0) is_same_subsquare=0, randompoint=mid;
        temp_rb=mid;
    }
    if(is_same_subsquare==1 && teehee==N){
        right_bound=N;
    }
    else{
        temp_lb=X0;
        temp_rb=randompoint;//FFF...FNNN...N
        while(temp_lb<temp_rb){
            int mid=(temp_lb+temp_rb+1)/2;
            if(examine(mid,Y0)) temp_lb=mid;
            else temp_rb=mid-1;
        }
        right_bound=temp_lb;
    }
    //left bound
    teehee=1;
    while(X0>teehee){
        if(examine(teehee,Y0)){
            break;
        }
        randompoint=teehee;
        teehee=(X0+teehee+1)/2;
    }
    //Check same subsquare
    is_same_subsquare=1;
    temp_lb=teehee;
    for(int i=0;i<2;i++){
        int mid=(X0+temp_lb+1)/2;
        if(examine(mid,Y0)==0) is_same_subsquare=0, randompoint=mid;
        temp_lb=mid;
    }
    if(is_same_subsquare==1 && teehee==1){
        left_bound=1;
    }
    else{
        int temp_rb=X0;
        temp_lb=randompoint;//NNN...NFFF...F
        while(temp_lb<temp_rb){
            int mid=(temp_lb+temp_rb)/2;
            if(examine(mid,Y0)) temp_rb=mid;
            else temp_lb=mid+1;
        }
        left_bound=temp_lb;
    }
    //up bound
    teehee=N;
    while(Y0<teehee){
        if(examine(X0,teehee)){
            break;
        }
        randompoint=teehee;
        teehee=(Y0+teehee)/2;
    }
    //Check same subsquare
    is_same_subsquare=1;
    temp_rb=teehee;
    for(int i=0;i<2;i++){
        int mid=(Y0+temp_rb)/2;
        if(examine(X0,mid)==0) is_same_subsquare=0, randompoint=mid;
        temp_rb=mid;
    }
    if(is_same_subsquare==1 && teehee==N){
        up_bound=N;
    }
    else{
        temp_lb=Y0;
        temp_rb=randompoint;//FFF...FNNN...N
        while(temp_lb<temp_rb){
            int mid=(temp_lb+temp_rb+1)/2;
            if(examine(X0,mid)) temp_lb=mid;
            else temp_rb=mid-1;
        }
        up_bound=temp_lb;
    }
    int M=right_bound-left_bound+1;
    down_bound=up_bound-M+1;
    for(int i=-4;i<=4;i++){
        for(int j=-4;j<=4;j++){
            int newX=X0+i*M;
            int newY=Y0+j*M;
            if(newX-2*M<1 || newX+2*M>N || newY-2*M<1 || newY+2*M>N) continue;
            if(abs(i)+abs(j)>4 || abs(i)+abs(j)==3 || abs(i)+abs(j)==1)continue;
            if(examine(newX-2*M,newY)==0)continue;
            if(examine(newX+2*M,newY)==0)continue;
            if(examine(newX,newY-2*M)==0)continue;
            if(examine(newX,newY+2*M)==0)continue;
            up_bound+=j*M;
            down_bound+=j*M;
            left_bound+=i*M;
            right_bound+=i*M;
            solution((left_bound+right_bound)/2,(down_bound+up_bound)/2);
            return;
        }
    }
}
signed main(){
    int N,X0,Y0;
    cin >> N >> X0 >> Y0;
    findCenter(N,X0,Y0);
}

Compilation message

aliens.cpp: In function 'void findCenter(long long int, long long int, long long int)':
aliens.cpp:106:29: warning: 'temp_rb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |             int mid=(temp_lb+temp_rb+1)/2;
      |                      ~~~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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