oj.uz

Submission #210849

# Submission time Handle Problem Language Result Execution time Memory
210849 2020-03-18T21:21:51 Z tatyam Aliens (IOI07_aliens) C++17
100 / 100
 10 ms 420 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(a) for(ll i = 0; i < a; i++)
#define all(a) begin(a), end(a)
#define sum(a) accumulate(all(a), 0LL)

ll n;
bool query(ll x, ll y){
    if(x < 1 || y < 1 || x > n || y > n) return false;
    cout << "examine " << x << ' ' << y << endl;
    string ans;
    cin >> ans;
    return ans[0] == 't';
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> n >> x >> y;
    ll ng = 0, ok = 1;
    while(query(x - ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x - cen, y)) ng = cen;
        else ok = cen;
    }
    x -= ng;
    ng = 0; ok = 1;
    while(query(x, y - ok)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x, y - cen)) ng = cen;
        else ok = cen;
    }
    y -= ng;
    ng = 0; ok = 1;
    while(query(x + ok, y)){
        ng = ok;
        ok *= 2;
    }
    while(ok - ng > 1){
        ll cen = (ok + ng) / 2;
        if(query(x + cen, y)) ng = cen;
        else ok = cen;
    }
    ll m = ok;
    x += m / 2;
    y += m / 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x - m * 2, y)) x -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x, y - m * 2)) y -= m * 2;
    if(query(x - m, y - m)){
        x -= m;
        y -= m;
    }
    x += m * 2;
    y += m * 2;
    cout << "solution " << x << ' ' << y << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 276 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 7 ms 248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 276 KB Output is correct
2 Correct 7 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 420 KB Output is correct
2 Correct 7 ms 248 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 296 KB Output is correct
2 Correct 7 ms 248 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Output is correct
2 Correct 6 ms 248 KB Output is correct
3 Correct 9 ms 404 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 8 ms 248 KB Output is correct
3 Correct 7 ms 376 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 252 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct

Subtask #10
10.0 / 10.0

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