oj.uz

Submission #508773

# Submission time Handle Problem Language Result Execution time Memory
508773 2022-01-13T17:46:24 Z kevinxiehk Aliens (IOI07_aliens) C++17
100 / 100
 3 ms 280 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

int examine(int X, int Y) {
    cout << "examine " << X << ' ' << Y << endl;
    string s;
    cin >> s;
    return s == "true";
}
void solution(int x, int y) {
    cout << "solution " << x << ' ' << y << endl;
    return;
}

// TODO: global variables can be declared here
int n;
int yes(int x,int y){
    if(min(x,y)<=0||max(x,y)>n)return false;
    return examine(x,y);
}
pair<int,int>border(int dx,int dy,int x0,int y0){
    int step=1;
    int x=x0,y=y0;
    while(yes(x0+step*dx,y0+step*dy))step*=2;
    int lx=x0+step/2*dx,rx=x0+step*dx;
    int ly=y0+step/2*dy,ry=y0+step*dy;
    while(!(lx==rx&&ly==ry)){
        int mx=(lx+rx+dx)/2;
        int my=(ly+ry+dy)/2;
        if(yes(mx,my)){
            lx=mx;ly=my;
        }
        else{
            rx=mx-dx;ry=my-dy;
        }
    }
    return make_pair(lx,ly);
}
void findCenter(int N, int X0, int Y0) {
    // TODO: implementation
    n=N;
    int l=border(-1,0,X0,Y0).first;
    int r=border(1,0,X0,Y0).first;
    int d=border(0,-1,X0,Y0).second;
    int m=r-l+1;
    int mx=l+m/2;
    int my=d+m/2;
    m*=2;
    if(yes(mx+m,my)&&!yes(mx-m,my)){
        if(yes(mx+m*2,my))mx+=m;
        else mx+=m/2,my+=m/2;
    }
    else if(!yes(mx+m,my)&&yes(mx-m,my)){
        if(yes(mx-m*2,my))mx-=m;
        else mx-=m/2,my+=m/2;
    }
    if(!yes(mx,my-m))my+=m;
    if(!yes(mx,my+m))my-=m;
    solution(mx,my);
    return;
}
signed main() {
    int n, x0, y0;
    cin >> n >> x0 >> y0;
    findCenter(n, x0, y0);
    return 0;
}

Compilation message

aliens.cpp: In function 'std::pair<long long int, long long int> border(long long int, long long int, long long int, long long int)':
aliens.cpp:24:9: warning: unused variable 'x' [-Wunused-variable]
   24 |     int x=x0,y=y0;
      |         ^
aliens.cpp:24:14: warning: unused variable 'y' [-Wunused-variable]
   24 |     int x=x0,y=y0;
      |              ^

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 280 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 280 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 200 KB Output is correct
3 Correct 1 ms 200 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 1 ms 204 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 200 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 2 ms 200 KB Output is correct
3 Correct 3 ms 200 KB Output is correct