oj.uz

Submission #444694

# Submission time Handle Problem Language Result Execution time Memory
444694 2021-07-14T21:06:18 Z yfhuang Aliens (IOI07_aliens) C++17
100 / 100
 2 ms 328 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pi;

ll n, X0, Y0;

bool in(ll x, ll y){
    return x >= 1 and x <= n and y >= 1 and y <= n;
}

bool ask(ll x, ll y){
    if(!in(x, y)) return 0;
    cout << "examine " << x << " " << y << endl;
    cout.flush();
    string s;
    cin >> s;
    return s == "true";
}

void answer(ll x, ll y){
    cout << "solution " << x << " " << y << endl;
    cout.flush();
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> X0 >> Y0; 
    ll l = 0, r = 0;
    for(ll i = 1;;i *= 2){
        if(!ask(X0 - i, Y0)){
            r = i; 
            break;
        }
    }
    while(l < r){
        ll mid = (l + r + 1) / 2;
        if(ask(X0 - mid, Y0)){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll xL = X0 - l;
    l = 0, r = 0;
    for(ll i = 1;;i *= 2){
        if(!ask(X0 + i, Y0)){
            r = i;
            break;
        }
    }
    while(l < r){
        ll mid = (l + r + 1) / 2;
        if(ask(X0 + mid, Y0)){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll xR = X0 + l; 
    ll m = xR - xL + 1;
    l = 0, r = 0;
    for(ll i = 1;;i *= 2){
        if(!ask(X0, Y0 - i)){
            r = i; 
            break;
        }
    }
    while(l < r){
        ll mid = (l + r + 1) / 2;
        if(ask(X0, Y0 - mid)){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll yL = Y0 - l;
    ll yR = yL + m - 1;
    X0 = xL, Y0 = yL;
    while(true){
        if(ask(X0 - 2 * m, Y0)){
            X0 -= 2 * m;
            continue;
        }
        if(ask(X0, Y0 - 2 * m)){
            Y0 -= 2 * m;
            continue;
        }
        if(ask(X0 - m, Y0 - m)){
            X0 -= m;
            Y0 -= m;
            continue;
        }
        break;
    }
    answer(X0 + 5 * m / 2, Y0 + 5 * m / 2);        
    return 0;
}

Compilation message

aliens.cpp: In function 'int main()':
aliens.cpp:84:8: warning: unused variable 'yR' [-Wunused-variable]
   84 |     ll yR = yL + m - 1;
      |        ^~

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

Subtask #4
10.0 / 10.0

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